sort 이해하기

Bubble sort, Insertion sort, Selection sort, Quick sort가 각각 어떤 방식으로 동작하는지 이해하고 코드를 통해 확인한다.

1. Bubble sort (거품 정렬)

• 서로 인접한 두 원소를 검사해서 정렬하는 알고리즘이다.
• 인접한 두 수를 비교해서 크기가 순서대로 되어있지 않으면 서로 교환한다.
• 비교해서 하나도 바꿀게 없을 때까지 비교하고, 반복한다.
• 시간복잡도: O(N^2)

1st

5 1 4 2 8 => 1 5 4 2 8 swap since 5 > 1

1 5 4 2 8 => 1 4 5 2 8 swap since 5 > 4

1 4 5 2 8 => 1 4 2 5 8 swap since 5 > 2

1 4 2 5 8 => 1 4 2 5 8 does not swap since 8 > 5

2nd

1 4 2 5 8 => 1 4 2 5 8 does not swap since 4 > 1

1 4 2 5 8 => 1 2 4 5 8 swap since 4 > 2

1 2 4 5 8 => 1 2 4 5 8 does not swap since 5 > 4

1 2 4 5 8 => 1 2 4 5 8 does not swap since 8 > 5

3rd

1 2 4 5 8 => 1 2 4 5 8 does not swap since 2 > 1

1 2 4 5 8 => 1 2 4 5 8 does not swap since 4 > 2

1 2 4 5 8 => 1 2 4 5 8 does not swap since 5 > 4

1 2 4 5 8 => 1 2 4 5 8 does not swap since 8 > 5

bubble sort C++ 코드

void bubblesort(int *list, int n) {
  int i, j, temp;

  for (i=0;i<n-1;i++){
    for (j=0;j<n-i-1;j++){
      if (list[j] > list[j+1]) {
        temp = list[j];
        list[j] = list[j+1];
        list[j+1] = temp;
      }
    }
  }
}

2. Insertion sort (삽입 정렬)

• 하나씩 들고 순서에 맞게 끼워넣는다.
• 작은 것부터 정렬된다.
• 카드 게임할 때 카드 섞는 것과 비슷하다.
• “Stable” - 똑같은 수 두개의 순서를 바꾸지 않는다. (순서가 섞이지 않는다! )
• “In-place” - 추가적인 메모리 공간을 필요로 하지 않는다. (bubble sort, seclection도 마찬가지)
• “Online” - 받는 즉시 바로 정렬할 수 있다.
• 하나의 element가 한번 정렬하면, 바로 정렬된 리스트로 삽입된다.
• 시간복잡도: O(1)

insertion sort C++ 코드

void insertionSort(int *list, int n) {
	for (int i = 1; i < n; i++) {
		int key = list[i];
		int j = i - 1;
		// move elements of list[0..i-1], that are greater than key,
		// to one position ahead of their current position
		while (j >= 0 && key < list[j]) {
			list[j + 1] = list[j];
			j = j - 1;
		}
		list[j + 1] = key;
	}
}

3. Selection sort (선택 정렬)

• 반복할 때 마다 가장 작은 element를 골라서 unsorted list의 맨 앞에다가 둔다. 즉, 가장 작은 수를 찾아서 현 위치랑 바꾼다.

• sorted 부분과 unsorted 부분이 나뉘어진다.

• “Unstable”: 똑같은 수가 두개있을 때, 둘의 순서가 바뀔 수 있다.

  => 예를 들어, 5 2 9 5 4 3 1 6인 경우, 5(a) 2 9 5(b) 4 3 1 6 가 한 회 돌고 나면, 1 2 9 5(b) 4 3 5(a) 6 이렇게 된다. 숫자 5가 뒤바뀌었다.

• 시간복잡도: O(N^2)

selection sort C++ 코드

void selectionSort(int *list, int n) {
	for (int i = 0; i < n - 1; i++) {
		int min = i;
		for (int j = i + 1; j < n; j++)
			if (list[j] < list[min]) 
				min = j;
		swap(list[i], list[min]);  // Swap min found with the first one of unsorted
	}
}

4. Quick sort (퀵 정렬)

• Divide and conquer 알고리즘
• sub-array는 recursive(재귀적)하게 정렬된다.

• 임의의 pivot을 정해서, 나머지 element 들을 **pivot보다 작은 것들 (좌측)과 pivot보다 큰 것들 (우측) **로 나눈다.

• 퀵정렬의 간단한 설명
  1. i와 j가 교차될 때 까지 다음을 반복한다.
     • i번째에 있는 값이 pivot보다 큰 값이 나올 때 까지 왼쪽에서 오른쪽으로 스캔한다.
     • j번째에 있는 값이 pivot보다 작은 값이 나올 때까지 오른쪽에서 왼쪽으로 스캔한다.
     • i번째에 있는 값과 j번째에 있는 값을 교환한다.
  2. i와 j가 교차가 되면,
     • pivot값과 j번째에 있는 값을 교환한다.

quick sort C++ 코드

/* This function takes last element as pivot, places the pivot element at its
correct position in sorted array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right of pivot */
int partition(int list[], int lo, int hi) {
	int x = list[hi];  // pivot
	int i = (lo - 1);  // Index of smaller element

	for (int j = lo; j <= hi - 1; j++) {
		if (list[j] <= x) { 				// if current element is <= pivot
			i++;    									// increment index of smaller element
			swap(list[i], list[j]);  	// Swap current element with index
		}
	}
	swap(list[i + 1], list[hi]);
	return (i + 1);
}

// QuickSort helper function for recursive operation
void _quickSort(int *list, int lo, int hi, int n) {
	if (lo < hi) 	{
		int pi = partition(list, lo, hi); // Partitioning index
		_quickSort(list, lo, pi - 1, n);
		_quickSort(list, pi + 1, hi, n);
	}
}

void quickSort(int *a, int n) {
	_quickSort(a, 0, n - 1, n);  
}