정렬 알고리즘 시간 복잡도
| Bubble Sort (버블 정렬) | O(n^2) |
| Selection Sort (선택 정렬) | O(n^2) |
| Insertion Sort (삽입 정렬) | O(n^2) |
| Quick Sort (퀵 정렬) | 평균 : O(nlogn) / 최악 : O(n^2) |
| Merge Sort (병합 정렬) | O(nlogn) |
| Radix Sort (기수 정렬) | O(kn) / k : 최대 데이터의 자릿수 |
| Arrays.sort() | 평균 : O(nlogn) / 최악 : O(n^2) |
| Collections.sort() | O(nlogn) |
1. 버블정렬
1.1 개념
- 순서대로 보면서 두 수를 비교해서 오른쪽 수가 왼쪽수보다 더 작으면 교화
- 한번 작업 시 → 맨 마지막 자리에 가장 큰수가 가게 되는 원리
- 즉, 마지막을 제외하고 n-1번 작업을 하면 정렬완료
- 시간 복잡도 O(n^2)
- 예시 → 3 4 1 5 2
- 1번째: 3 4 1 5 2 → 3 1 4 5 2 →3 1 4 2 5 : 5 확정
- 2번째: 3 1 4 2 5 → 1 3 4 2 5 → 1 3 2 4 5 : 4 확정
- 3번째: 1 3 2 4 5 → 1 2 3 4 5 : 3 확점
- 4번째: 1 2 3 4 5 : 1,2 확정
1.2 코드
//정럴할 수 입력받기
for(int i=0; i<size; i++){
bubble[i] = Integer.parseInt(st.nextToken());
}
//버블정렬
for(int i =0; i<size-1; i++){ //n-1번 작업
boolean change = false; //요소 위치 변경되었는지 나타내는 변수 위치 변경 안되었다면 이미 정렬이므로 break
for(int j=0; j<size -1 -i; j++){ //현재 요소와 다음 요소를 비교하여 큰 값을 뒤로 보내기 위한 역할
if(bubble[j]>bubble[j+1]){ //첫번째 수가 두번째 수보다 크면 바꾸기
change = true;
int tmp = bubble[j];
bubble[j] = bubble[j+1];
bubble[j+1] = tmp;
}
}
if(!change) break; //위치 변경 안되었다면 이미 정렬이므로 break
}
System.out.println(Arrays.toString(bubble));
2. 선택정렬
2.1 개념
- for문을 통해 가장 작은 값을 찾고, 맨 앞자리랑 교환
- 그 다음 for문에서는 맨앞자리 제외한 값중에 가장 작은 갑 착고, 두번째 자리랑 교환
- n-1번 작업
- 시간복잡도: O(n^2)
- 예시 → 3 4 1 5 2
- 1번째: 최소값 1 이랑 첫번째 자리수 3이랑 바꾸기 → 1 4 3 5 2 : 1확정
- 2번째: 최소값 2랑 두번째 자리수 4랑 바꾸기 → 1 2 3 5 4 : 2확정
- 3번째: 최소값 3 이미 세번째 자리수임 : 3확정
- 4번째: 최솟값 4랑 4번째 자리수 5랑 바꾸기 : 4확정 , 5확정
2.2 코드
//선택정렬
for(int i =0; i<size-1; i++){
int min_index = i; //가장 작은 인덱스 첫번째로 두고 시작
//가장 작은 수 찾기
for(int j = i+1; j<size; j++){
if(arr[min_index]>arr[j]){
min_index = j; //j로 작은인덱스 바꾸기
}
}
//가장 작은수랑 i번째 수랑 바꾸기
int tmp = arr[min_index];
arr[min_index] = arr[i];
arr[i] = tmp;
}
3. 삽입정렬
3.1 개념
- for문을 돌리면서 해당 index가 index 앞까지의 부분에서 삽입될 위치를 찾아 삽입
- 최대 n-1번 반복
- 시간복잡도: O(n^2)
- 삽입될 위치 찾을 때 이진탐색으로 탐색하면 시간복잡도 줄일 수 있음
- 예시 → 3 4 1 5 2
- 2번째 값 = 4 → 3 4 1 5 2
- 3번째 값 = 1 : 3,4 보다 앞에 삽입 → 1 3 4 5 2
- 4번째 값 = 5 → 1 3 4 5 2
- 5번째 값 = 2 → 1,3 사이에 삽입 → 1 2 3 4 5
3.2 코드
for (int i = 1; i < size; i++) { //1부터 마지막까지
int tmp = arr[i]; //1번째 값 tmp 에 넣기
for(int j = i; j>=0; j--){
if(j==0){
arr[0] = tmp; //앞으로 가면서 전부 확인했지만 맨앞에 숫자를 넣어야함(tmp가 가장 작은수였음)
}else if(arr[j-1] <= tmp){ //tmp 값이랑 그 이전 값부터 앞으로 비교 -> tmp가 더 큼 == 이미 tmp가 가야할 곳 찾음
arr[j] = tmp; //tmp를 현재위치에 저장하고 break
break;
}else{
//아직 tmp가 앞으로 더 갈일이 남음 arr[j-1]값을 현재값 arr[j]값으로 덮어씀
arr[j] = arr[j-1];
}
}
}
4. 퀵정렬
4.1 개념
- 분할 정복 방법을 통해 주어진 배열을 정렬
- 불안정 정렬, 분할 정렬
- 문제를 작은 2개의 문제로 분리하고 각각을 해결 → 결과를 모아 원래의 문제를 해결하는 방법
- 예시) 오름차순일 경우
- 배열 가운데 하나의 원소 고르기(피벗)
- 피벗을 기준으로 비균등하게 2개의 부분 배열로 분할
- 피벗을 기준으로 피벗 앞에는 피벗보다 작은 수가, 오른쪽에는 피벗보다 큰 수가 옮겨짐
- 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬(피벗을 다시 선택해 정렬을 반복)
- 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복
0)초기배열
6 9 20 3 5 10 7 11 15 1
1)배열의 가장 왼쪽 숫자를 피벗 값으로 설정
6 9 20 3 5 10 7 11 15 1
2)피벗값을 기준으로 나머지 값들에 대해 왼쪽부터는 피벗값보다 큰 값을, 오른쪽부터는 피벗값보다 작은 값을 찾음
큰 값은 9, 작은 값은 1으로 둘의 위치를 교환해 주고 반복
6 9 20 3 5 10 7 11 15 1
6 1 20 3 5 10 7 11 15 9
6 1 20 3 5 10 7 11 15 9
6 1 5 3 20 10 7 11 15 9
3)큰 값의 인덱스가 작은 값의 인덱스보다 더 높아지면 둘 중 작은 값을 피벗값과 교환, 이 때 피벗값은 정렬위치가 확정
3 1 5 6 20 10 7 11 15 9
4)6의 왼쪽 집합과 오른쪽 집합에서 각각 첫 번째 요소를 피벗으로 지정하고 두 집합의 퀵 정렬을 동시에 수행
3 1 5 **6** 20 10 7 11 15 9
3 1 5 **6** 20 10 7 11 15 9
1 3 5 **6** 20 10 7 11 15 9
**1 3 5 6** 20 10 7 11 15 9
**1 3 5 6** 20 10 7 11 15 9
**1 3 5 6** 9 10 7 11 15 **20**
**1 3 5 6** 9 10 7 11 15 **20**
**1 3 5 6** 9 10 7 11 15 **20**
**1 3 5 6** 9 7 10 11 15 **20**
**1 3 5 6 7 9** 10 11 15 **20**
**1 3 5 6 7 9 10** 11 15 **20**
**1 3 5 6 7 9 10 11 15 20**
4.2 코드
public class QuickSort {
public static void main(String[] args) {
int[] arr = { 3, 1, 5, 6, 20, 10, 7, 11, 15, 9 };
quickSort(arr);
}
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int start, int end) {
// start가 end보다 크거나 같다면 정렬할 원소가 1개 이하이므로 정렬하지 않고 return
if (start >= end)
return;
// 가장 왼쪽의 값을 pivot으로 지정, 실제 비교 검사는 start+1 부터 시작
int pivot = start;
int lo = start + 1;
int hi = end;
// lo는 현재 부분배열의 왼쪽, hi는 오른쪽을 의미
// 서로 엇갈리게 될 경우 while문 종료
while (lo <= hi) {
while (lo <= end && arr[lo] <= arr[pivot]) // 피벗보다 큰 값을 만날 때까지
lo++;
while (hi > start && arr[hi] >= arr[pivot]) // 피벗보다 작은 값을 만날 때까지
hi--;
if (lo > hi) // 엇갈리면 피벗과 교체
swap(arr, hi, pivot);
else
swap(arr, lo, hi); // 엇갈리지 않으면 lo, hi 값 교체
}
// 엇갈렸을 경우,
// 피벗값과 hi값을 교체한 후 해당 피벗을 기준으로 앞 뒤로 배열을 분할하여 정렬 진행
quickSort(arr, start, hi - 1);
quickSort(arr, hi + 1, end);
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
5. 병합정렬
5.1 개념
- n개의 입력값 ⇒ n개의 그룹으로 나누고 2개씩 그룹을 합치면서 동시에 정렬
- 1개의 그룹이 남을때까지 반복하면 정렬 완료
- 시간복잡도: O(nlongn)
- 삽입될 위치 찾을 때 이진탐색으로 탐색하면 시간복잡도 줄일 수 있음
- 예시 → 3 4 1 5 2 8 7 6
- 8개 그룹: 3, 4, 1, 5, 2, 8, 7, 6
- 4개 그룹: (3, 4), (1, 5), (2, 8), (6 ,7)
- 2개 그룹: (1, 3, 4, 5), (2, 6, 7, 8)
- 1개 그룹: (1, 2, 3, 4, 5, 6, 7, 8)
- (1, 3, 4, 5) (2, 6 ,7, 8) 그룹 합치는 방법
- 첫번째 그룹의 첫번째 숫자와 두번째 그룹의 첫번째 숫자 비교 → 1이 더 작음
- 합치는 그룹에 1을 넣어줌 : (1,
- 첫번째 그룹의 두번째 숫자와 두번째 그룹 첫번째 숫자 2랑 비교 → 2가 더 작음
- 합치는 그룹에 2 넣어줌 : (1, 2,
- 첫번째 숫자의 두번째 숫자(3)와 두번째 그룹의 두번째 숫자(6)랑 비교 → 3이 더 작음
- 합치는 그룹에 3 넣어줌 : (1, 2, 3
- 이런식으로 끝까지 모든 숫자 합
5.2 코드
private static int[] arr;
private static int[] tmp;
public static void mergeSort(int start, int end){
if(end - start < 1) return; //이미 정렬된 상태이기 때문에 리턴
int middle = (start + end)/2; // 반 나누기
mergeSort(start, middle);
mergeSort(middle+1, end);
tmp = new int[arr.length]; //임시 배열 초기화
//임시 배열에 정렬된 값 복사
for(int i = start; i<= end; i++){
tmp[i] = arr[i];
}
//왼쪽, 오른쪽 합병할 때 사용할 인덱스변수 초기화
int left = start;
int right = middle + 1;
int index = start;
//왼쪽과 오른쪽 부분을 합병하면정렬된 값을 원래 배열(arr)에 넣음, 작은 값을 가진 값부터 차례대로 병합됨
while (left <= middle && right <= end) {
if (tmp[left] <= tmp[right]) {
arr[index++] = tmp[left++];
} else {
arr[index++] = tmp[right++];
}
}
// 남은 왼쪽 부분 배열 복사
while(left <= middle) {
arr[index ++] = tmp[left ++];
}
//남은 오른쪽 부분 배열 복사
while(right <= end) {
arr[index ++] = tmp[right ++];
}
7. 계수정렬
7.1 개념
- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용
- 숫자끼리 비교하지 않고, 카운트를 세서 정렬하는 방식
- 카운팅을 위한 메모리 필요
- O(n+k)
- k는 정렬 대상 데이터 중 최대값으로, k가 n보다 더 커서 worst한 케이스를 만들 수 있음
- 정렬과정
- 원소 중 가장 큰 값으로 배열 사이즈를 잡아서, 카운팅 테이블을 만든다
- 각 위치의 값을 카운팅 개수만큼 뽑아준다
7.2 코드
public static void countingSort(int[] arr){
//최댓값 구해서 배열 설정
int max = Arrays.stream(arr).max().getAsInt(); //최대값 구함
int[] cntArr = new int[max + 1]; //카운팅 테이블 생성
for (int i = 0; i < arr.length; i++) {
cntArr[arr[i]]++; //각 값에 대해 해당 카운팅 테이블의 값 수정
}
int idx = 0;
//카운팅 테이블의 값을 뽑아내며 arr 배열에 정렬
for(int i = 0; i < cntArr.length; i++){
while(cntArr[i]>0){
arr[idx++] = i; // cnt[10] = 2 였다면, 10 이라는 값이 두번 나왔으므로 arr[0] = 10, arr[1] = 10 삽입
cntArr[i] -= 1;
}
}
}
8. 기수정렬
8.1 개념
- 입력되는 수의 개수가 많지만, 수의 범위가 적을때 사용하면 유용
- 10개의 Queue(FIFO)가 필요 (0~9번째 큐)
- 0번째 큐: 일의 자리가 0인 숫자, 1번째 큐: 일의자리가 1인 숫자.. 큐 설정
- 0번째 큐부터 9번째 큐까지 돌면서 순서대로 poll
- 그 이후에는 십의자리 기준 → 백의자리 기준 .. 순서로
- 이 작업을 최대 k(최대 숫자의 자릿수)번 반복하면 정렬 완료
- 시간복잡도: O(kn)
- 195 10 5 7 25 61 255 36 4 를 정렬한다고 가정
- 일의자리 기준
- 0번째 큐: 10
- 1번째 큐: 61
- 4번째 큐: 4
- 5번째 큐: 195 5 25 255
- 6번째 큐: 36
- 7번째 큐: 7
- 2, 3, 8, 9째 큐는 비어있음
- 큐 순서대로 poll하면
- 10 61 4 195 5 25 255 36 7
- 십의자리기준으로 작업 마치면
- 4 5 7 10 25 36 255 61 195
- 백의 자리 기준으로 작업 마치면
- 4 5 7 10 25 36 61 195 255
- ⇒ 최대 자릿수가 3이니까 정렬완료
- 4 5 7 10 25 36 61 195 255
- 일의자리 기준
8.2 코드
public static void radixSort(int[] arr) {
int max = 0, maxSize = 1;
//가장 큰수 구하기
for (int num : arr) {
if (max < num) max = num;
}
//가장 큰수의 자릿수 구해야 그만큼 반복해야함
while(max>=10){
maxSize++;
max/=10;
}
//Queue 배열 생성
LinkedList[] queues = new LinkedList[10]; //0~9로 총 10개
for(int i = 0; i<=9; i++){
queues[i] = new LinkedList<>();
}
//기수정렬
int t = 1, index;
for(int i = 1; i<=maxSize; i++){ //자릿수만큼 전체 for문
for(int j = 0; j<arr.length; j++){ //배열의 모든 요소 순회
queues[(arr[j]/t)%10].add(arr[j]); //
//(arr[j]/t)%10 : 현재 arr[j]의 자릿수 구함 => 195면 5를 구하기(t=1일때 이므로 일의자리수 5)
//현재 자릿수(t)에 해당하는 숫자를 기준으로 큐에 숫자 추가
}
index = 0; //인덱스 0으로 초기화
//큐를 돌면서 큐에 값이 있을때 그 값을 꺼내서 배열에 저장
for(int j = 0; j<=9; j++){
while(!queues[j].isEmpty()){
arr[index++] = Integer.parseInt(queues[j].poll().toString());
}
}
t *= 10; //다음 자릿수는 10곱합
}
}
비트마스킹
- 비트 마스킹이란?
- 정수의 이진수 표현을 자료구조로 쓰는 기법으로 0, 1로 true/false, on/off와 같은 상태를 나타내는 것이 가능하다.
- 비트 마스크의 장점
- 빠른 수행시간 - 비트 마스킹은 bit연산이므로 거의 모든 연산이 O(1)의 시간 복잡도를 갖고 있다.
- 간결한 코드 - 다양한 집합 연산을 비트 연산자를 이용하여 한 줄로 작성이 가능하다.
- 작은 메모리 사용량 - 1bit로 상태 저장이 가능하므로 메모리 사용량이 적어 DP에 유리하다.
- 비트 연산자
비트 연산자 논리 의미
| & | AND | 양쪽 비트가 모두 1인 경우에만 1, 나머지 모든 경우 0 |
| OR | ||
| ^ | XOR | 양쪽 비트가 서로 다른 경우 1, 같은 경우 0 |
| ~ | NOT | 비트 반전 (0이면 1, 1이면 0) |
| << | SHIFT | 정수 a를 왼쪽으로 b비트 만큼 이동 (빈자리를 0으로 채움, MSB가 바뀌면 양수 <-> 음수) |
| >> | 정수 a를 오른쪽으로 b비트 만큼 이동 (빈자리 최상위 비트(MSB)로 채움) | |
| >>> | 정수 a를 오른쪽으로 b비트 만큼 이동 (빈자리 0으로 채움) |
- 비트 마스크로 집합 연산
연산 예시 코드 설명
| 공집합 | 변수 = ((1 << A) - 1); | 0 반환 |
| 꽉 찬 집합 | A의 개수만큼 비트 켜짐(1) | |
| 원소 추가 | A | = (1 << k); |
| 원소 삭제 | A &= ~(1 <<k); | k번째 비트 끄기 |
| 원소 포함 여부 | A & (1 << k) == (1 << k) | 집합 A에서 k 번째 비트의 켜짐, 꺼짐 확인 |
| 원소 토글 | A ^= (1 << k); | k번째 비트 반전 |
| 두 집합 연산 | A | B |
| A & B | 집합 A와 집합 B의 교집합 | |
| A & -B | 집합 A - 집합 B (차집합) | |
| A ^ B | 집합 A와 집합 B의 합집합 - 교집합 (XOR) | |
| 집합의 크기 | Integer.bitCount(A); | 집합 A내 켜진 비트수 반환 |
| 최소 원소 찾기 | 변수 = A & (-A); | 집합 A에서 켜져있는 비트 중 최소 비트 반환 |
| 최소 원소 삭제 | A &= A-1; | 집합 A에서 켜져있는 비트 중 최소 비트 끄기 |
| 부분 집합 순회 | for (int i = A; i; i =((i - 1) & A) {} | 집합 A의 부분집합 순회 |
- BitSet
- BitSet은 java.util에 있는 자료구조
- 원소가 0 또는 1인 배열처럼 사용됨
- 선언 및 초기화
BitSet set = new BitSet(size); (size입력 안하면 크기 64로 초기화)
- n 번째 비트 추가
set.set(n);
- n 번째 비트 삭제
set.clear(n);
- n 번째 비트 반전
set.flip(n):
- 1비트의 개수 반환
set.cardinality();
- 교집합, 차집합, 합집합, 대칭 차집합 (= 합집합 - 교집합)
set1.and(set2) - set1과 set2의 교집합을 set1에 저장
set1.andNot(set2) - set1과 set2의 차집합을 set1에 저장
set1.or(set2) - set1과 set2의 합집합을 set1에 저장
set1.xor(set2) - set1과 set2의 대칭 차집합을 set1에 저장
- NOT (연산의 경우 자료형에 따라 결과가 달라짐 주의)
- ex) A = 83 = 10100112
- 8비트 자료형의 경우 ~A = 101011002
- 32비트 자료형인 경우 ~A = 11111111 11111111 11111111 101011002
- ex) A = 83 = 10100112
- AND
- 1010 & 1111 = 1010
- OR
- 1010 | 1111 = 1111
- XOR
- 1010 | 1111 = 0101
- NOT
- ~1010 = 0101
- SHIFT
- 00001010 << 2 = 101000
- 00001010 >> 2 = 000010
- SHIFT 연산의 경우
- 왼쪽 시프트 → A × 2B
- 오른쪽 시프트 → A / 2B
- ex) (A + B) / 2 = (A + B) >> 2로 계산할 수도 있음
- 주의사항
- 연산자 우선순위가 낮음!
- int c = ( 6 & 4 == 4); 의 경우 4 == 4가 먼저 계산됨.
- 주의사항