[알고리즘] 정렬의 기본 - 선택, 버블, 삽입, 힙 정렬

선택 정렬

최소 원소를 찾고, 최소 원소를 제일 앞으로 보내는 것을 반복하면서 정렬한다. for루프를 (n-1) + (n-2) + (n-3) +... + 2 + 1번 반복하므로 시간 복잡도는 O(n^2)이다.

for(int i=0; i<arr.size()-1; i++){
  int min_index = i;
  for(int j=i+1; j<arr.sieze(); j++)
    if(arr[max_index] < arr[j]) min_index = j;
  swap(max_index, i);
}

---

버블 정렬

배열을 탐색하면서 이웃한 원소와 계속 비교하면서 순서가 잘못되어 있으면 교환하고 가장 큰 원소를 뒤로 보낸다. 여기서 최적화할 부분이 하나 있는데, 이웃한 원소와 비교하면서 swap 하는 과정에서 맨 마지막 원소는 이미 정렬되기에 검사할 필요가 없다는 것이다.

 

예를 들어 첫 번째 반복에서는 가장 큰 원소가 맨 뒤에 배치된다. 그 다음 반복에서는 마지막에서 두 번째 원소까지 정렬되어 있다. 마지막 반복에서는 첫 번째 원소와 두 번째 원소만 비교하면 된다.

 

시간복잡도는 선택정렬과 같다.

for(int i=0; i<arr.size()-1; i++){
  for(int j=0; j<arr.sieze()-i-1; j++){
    if(arr[j] > arr[j+1]) swap(j ,j+1);
    swap(j, j+1);
  }
}

---

삽입 정렬

이미 정렬된 배열에 정렬되지 않은 배열의 원소를 하나씩 더해서 정렬된 배열 하나로 만든다.

arr = [29, 10, 14, 37, 13]을 정렬해보자.

​

1. 정렬된 배열 res에 29 삽입

res = [29, null]

​

2. res에 10 삽입

res = [10, 29]

​

3. res에 14 삽입

res = [10, 14, 29]

​

... 위의 과정을 반복한다. 실제로는 값이 복사되면서 삽입된다.

​

시간 복잡도는 배열이 역으로 정렬되어 있는 Worst case에서 1 + 2 +... + (n-2) + (n-1) = θ(n^2), 배열이 이미 정렬되어있는 Best case에서 1 + 1 + ... + 1 = θ(n), 따라서 Average case에서는 (n^2 + n)/2 = n^2이다.

for(int i=1; i<arr.size();i++){
  //i-1번째 배열까지는 정렬된 배열이다.
  int temp = arr[i]; //i번째 원소를 정렬된 배열에 삽입한다.
  for(int j=i-1; j>=0; j--){
    if(arr[j] > temp) a[j+1] = a[j]; //삽입할곳이 더 앞에 있으면 j번째 원소를 한칸 뒤로 민다.
    else break; //삽입할 곳을 찾으면 j 다음칸에 삽입하면 된다.
  }
  arr[j+1] = temp;
}

​

---

힙 정렬

최대힙을 구성하고, 루트를 힙의 마지막 원소와 교환한다. 그 후 마지막 원소는 정렬된 배열의 뒤에서부터 앞 순서로 넣는다. 마지막 원소를 제외하고 나머지 원소에 대해 다시 힙을 만들고 교환하는 과정을 반복한다. log n의 heapify를 n번 호출하므로 시간 복잡도는 O(n long n)이다.

Build_Max_Heap(A) //최대힙 구성
  for(int i=A.size; i>1; i--){
  swap(1, i); //루트와 힙의 마지막 원소 교환
  A.size--;
  //루트노트들 제외하고는 모두 힙 특성에 맞으므로 루트만 맞게하면 된다.
  heapify(A, 1);
}