[실전 알고리즘] 정렬1(면접용)

기초 정렬

 

Selection Sort / O(N^2)

- swap으로 구현

int arr[10] = { 3,2,7,116,62,235,1,23,55,77 };
	int n = 10;
	for (int i = n - 1; i > 0; i--)
	{
		int maxIndex = 0;
		for (int j = 1; j <= i; j++)
		{
			if (arr[maxIndex] < arr[j])
			{
				maxIndex = j;
			}
		}
		swap(arr[maxIndex], arr[i]);
	}

 

- max_element 함수 이용하여 구현

int arr[10] = { 3,2,7,116,62,235,1,23,55,77 };
	int n = 10;
	for (int i = n - 1; i > 0; i--)
	{
		swap(*max_element(arr, arr + i + 1), arr[i]);
	}

 

Bubble Sort / O(N^2)

int arr[5] = {-2,2,4,6,13};
	int n = 5;
	for (int i = 0; i <n; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])swap(arr[j], arr[j + 1]);
		}
	}

 

Merge Sort / O(NlogN)

재귀적으로 수열을 나눠 정렬한 후 합치는 정렬법

출처 바킹독 알고리즘 강의

Merge Sort 연습

[백준 11728] 배열 합치기 (tistory.com)

 

 

Merge Sort 구현

#include <bits/stdc++.h>
using namespace std;

int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};
int tmp[1000001]; // merge 함수에서 리스트 2개를 합친 결과를 임시로 저장하고 있을 변수

// mid = (st+en)/2라고 할 때 arr[st:mid], arr[mid:en]은 이미 정렬이 되어있는 상태일 때 arr[st:mid]와 arr[mid:en]을 합친다.
void merge(int st, int en){
  int mid = (st+en)/2;
  int lidx = st; // arr[st:mid]에서 값을 보기 위해 사용하는 index
  int ridx = mid; // arr[mid:en]에서 값을 보기 위해 사용하는 index
  for(int i = st; i < en; i++){
    if(ridx == en) tmp[i] = arr[lidx++];
    else if(lidx == mid) tmp[i] = arr[ridx++];
    else if(arr[lidx] <= arr[ridx]) tmp[i] = arr[lidx++];
    else tmp[i] = arr[ridx++];
  }
  for(int i = st; i < en; i++) arr[i] = tmp[i]; // tmp에 임시저장해둔 값을 a로 다시 옮김
}

// a[st:en]을 정렬하고 싶다.
void merge_sort(int st, int en){
  if(en == st+1) return; // 리스트의 길이가 1인 경우
  int mid = (st+en)/2;
  merge_sort(st, mid); // arr[st:mid]을 정렬한다.
  merge_sort(mid, en); // arr[mid:en]을 정렬한다.
  merge(st, en); // arr[st:mid]와 arr[mid:en]을 합친다.
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  merge_sort(0, n);
  for(int i = 0; i < n; i++) cout << arr[i] << ' '; // -53 3 12 15 16 22 23 25 46 357
}

 

 

Stable Sort

우선 순위가 같은 원소들끼리는 원래의 순서를 따라가도록 하는 정렬

- 즉 정렬 전에 나이가 21살로 같은 사람들의 순서가 파랑, 빨강, 초록 순이니 정렬 후에도 이 순서는 같게 두는 것

- 그림에서의 첫 번째로 무조건 정렬이 되는 정렬 방법은 Stable Sort이고, 첫 번째로 무조건 정렬이 된다고 보장할 수 없고 두 번째나 세 번째로 정렬이 될 수도 있는 정렬 방법은 Unstable Sort.

- 머지 소트는 Stable Sort인데 이 성질을 만족시키려면 앞 리스트에서 현재 보는 원소와 뒤 리스트에서 현재 보는 원소의 우선 순위가 같을 때 앞 리스트의 원소를 먼저 보내줘야함 

 

 

Quick Sort

일반적으로는 퀵 소트가 거의 모든 정렬 알고리즘보다 빨라서 각종 라이브러리의 정렬은 대부분 퀵 소트를 바탕으로 만들어져 있음

그런데  코딩테스트에서 STL을 못 쓰고 직접 정렬을 구현해야 하면 절대절대절대절대절대절대 퀵 소트 쓰지 말고 머지 소트를 써야 함

 

 

pivot을 하나 잡고 pivot의 왼쪽은 pivot보다 작은 원소가, 오른쪽에는 pivot보다 큰 원소가 오게끔 반복해서 정렬

 

Quick Sort 장점:

추가적 공간이 필요하지 않음

배열 안에서의 자리 바꿈만으로 처리가 되기 때문에 cache hit rate가 높아서 속도가 빠르다는 장점

 

 

Quick Sort 구현

#include <bits/stdc++.h>
using namespace std;

int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};

void quick_sort(int st, int en) { // arr[st to en-1]을 정렬할 예정
  if(en <= st+1) return; // 수열의 길이가 1 이하이면 함수 종료.(base condition)
  int pivot = arr[st]; // 제일 앞의 것을 pivot으로 잡는다. 임의의 값을 잡고 arr[st]와 swap해도 상관없음.
  int l = st+1; // 포인터 l
  int r = en-1; // 포인터 r
  while(1){
    while(l <= r && arr[l] <= pivot) l++;
    while(l <= r && arr[r] >= pivot) r--;
    if(l > r) break; // l과 r이 역전되는 그 즉시 탈출
    swap(arr[l], arr[r]);
  }
  swap(arr[st], arr[r]);
  quick_sort(st, r);
  quick_sort(r+1, en);
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  quick_sort(0, n);
  for(int i = 0; i < n; i++) cout << arr[i] << ' ';
}

 

 

 

 

출처

BaaaaaaaarkingDog | [실전 알고리즘] 0x0E강 - 정렬 I (encrypted.gg)