선택정렬 Θ(n^2)
버블정렬 Θ(n^2)
삽입정렬 Θ(n^2) Θ(n)
선택정렬 Θ(n^2)
A[1..n]에서 가장 큰 원소를 찾아 이 원소와 배열의 맨 끝자리에 있는 A[n]과 자리를 바꾼다.
8 31 48 73 3 65 20 29 index 0~7중에 가장 큰 수의 위치를 찾아 index 7의 값과 바꾼다.
8 31 48 29 3 65 20 73 index 0~6중에 가장 큰 수의 위치를 찾아 index 6의 값과 바꾼다.
8 31 20 29 3 65 48 73 반복
8 31 20 29 3 65 48 73
8 3 20 29 31 65 48 73
8 3 20 29 31 65 48 73
8 3 20 29 31 65 48 73
3 8 20 29 31 65 48 73
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | public static void selectionSort(int []arr){ for(int i=arr.length-1 ; i>0 ; i--){ int biggestNum = i; for(int j=0 ; j<i ; j++){ if(arr[biggestNum]<arr[j]){ biggestNum = j; } } if(biggestNum!=i){ int temp = arr[i]; arr[i] = arr[biggestNum]; arr[biggestNum] = temp; } } } | cs |
PS)
알고리즘 책에서는 뒤에서부터 정렬해 나가지만
정보처리기사에서는 앞에서부터 정렬하게 나온다.
순서의 차이일뿐 똑같은 방법이기 때문에 상관없으려고 했는데
문제 풀때 헤깔려서 짜증난다.
버블정렬 Θ(n^2)
선택정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복하는 정렬
8 31 48 73 3 65 20 29 index 0과 index 1의 값을 비교해 큰 수를 뒤로 미룬다.
8 31 48 73 3 65 20 29 index 1과 index 2의 값을 비교해 큰 수를 뒤로 미룬다.
8 31 48 73 3 65 20 29 반복
8 31 48 73 3 65 20 29
8 31 48 3 73 65 20 29
8 31 48 3 65 73 20 29
8 31 48 3 65 20 73 29
8 31 48 3 65 20 29 73 index 7에 가장 큰 수가 왔으므로 선택정렬처럼 범위를 줄여서 반복한다.
1 2 3 4 5 6 7 8 9 10 11 | public static void bubbleSort(int []arr){ for(int i=arr.length-1;i>0;i--){ for(int j=0;j<i;j++){ if(arr[j]>arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } | cs |
삽입정렬 Θ(n^2) Θ(n)
이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개짜리 배열을 만드는 과정을 반복하는 정렬
정렬되어 있을수록 더 빠른 수행시간을 가진다.
완전히 정렬되어 있다면 Θ(n)의 시간이 든다.
8 31 48 73 3 65 20 29
8 31 48 73 3 65 20 29 1개짜리 정렬된 배열
8 31 48 73 3 65 20 29 2개짜리 정렬된 배열
8 31 48 73 3 65 20 29 3개짜리 정렬된 배열
8 31 48 73 3 65 20 29 4개짜리 정렬된 배열
3 8 31 48 73 65 20 29 5개짜리 정렬된 배열 (추가된 3을 맞는 위치에 가게 한다.)
3 8 31 48 65 73 20 29 반복
3 8 20 31 48 65 73 29
3 8 20 29 31 48 65 73
1 2 3 4 5 6 7 8 9 10 11 12 13 | public static void insertionSort(int []arr){ for(int i=1;i<arr.length;i++){ for(int j=i;j>0;j--){ if(arr[j-1]>arr[j]){ int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; }else{ break; } } } } | cs |