[Sorting] 버블정렬, 선택정렬, 삽입정렬

정렬은 데이터의 집합을 특정 기준을 두고 우선 순위에 맞게 데이터를 저장하는 것이다.

대표적인 예로 오름차순과 내림차순이 있다.

정렬에도 다양한 알고리즘이 있지만 오늘은 정렬하는데 O(n^2)의 시간이 필요한 Bubble, Selection, Insertion Sorting에 알아보려고 한다.

 

Bubble Sorting

버블 정렬은 서로 인접한 두 데이터를 비교하고 조건에 맞지 않으면 두 데이터의 위치를 바꾼다. 그러면서 모든 데이터들이 조건에 맞는 위치에 찾아가게 된다. 

• In-place Sorting(제자리 정렬) - 추가적인 메모리 공간을 필요로 하지 않음
• Stable Sorting(안정 정렬)

버블정렬 과정

정렬과정

1. 화살표는 현재 비교하려는 데이터이고 항상 자신의 오른쪽 데이터와 비교를 한다.
2. 따라서 화살표가 가리키는 데이터가 자신의 오른쪽 데이터보다 크면 자리를 교환한다.
3. 한바퀴가 다 돌면 마지막에 저장되는 데이터는 데이터 집합에서 가장 큰 값이다.
4. 마지막 인덱스 자리는 더 이상 비교할 필요가 없으므로 비교 조건에서 제외시킨다.

이 과정을 코드로 나타내면

void bubble(int arr[], int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < n - i; j++) {  // 코드를 간결하게 하고자 비교 대상을 왼쪽과 비교하게 했다.
			if (arr[j - 1] > arr[j])
				swap(&arr[j - 1], &arr[j]);
		}
	}
}

 

Selection Sorting

선택정렬은 모든 데이터를 한바퀴 돌면서 가장 작은 값을 찾는다. 그리고 가장 작은 값을 첫번째 인덱스와 바꾼다. 그리고 두번째 인덱스에서도 다음으로 가장 작은 값을 찾아서 넣는다. 여기서 핵심은 저장할 자리는 이미 정해진 것이고, 여기에 맞는 적당한 데이터를 찾는 것이다.

• In-place Sorting(제자리 정렬)
• Unstable Sorting(불안정 정렬) - 동일한 데이터들의 자리가 서로 바뀔 수 있는 경우
• ex) 2, 2`, 1, 3 의 경우를 생각해보자 

 

선택 정렬 과정

정렬과정

1. 첫번째 인덱스를 처음 저장할 위치로 설정하고 최소값을 갖는 인덱스를 저장할 변수를 초기화한다 .
2. 한바퀴 돌면서 최소값이 들어있는 인덱스가 있다면 minIndex변수에 저장한다.
3. 한바퀴를 다 돌았다면 최소값과 저장할 위치에 있는 데이터의 자리를 서로 교환한다.
4. 첫번째 인덱스는 이미 저장이 완료되었으므로 다음 탐색에서 제외한다.

이 과정을 코드로 나타내면

void selection(int arr[], int n) {
	int index;
	for (int i = 0; i < n; i++) {
		index = i;
		for (int j = i + 1; j < n; j++) {
			if (arr[index] > arr[j])
				index = j;
		}
        if(index != i)
		  swap(&arr[i], &arr[index]);
	}
}

 

Insertion Sorting

삽입정렬은 현재 가리키는 위치까지 모두 정렬이 완료된 것으로 간주하고 정렬이 완료된 데이터 내에 삽입할 데이터의 위치를 찾는다. 처음 시작은 첫번째 인덱스의 값은 이미 정렬된 것으로 보고 두번째 인덱스의 값부터 시작하여 자신이 들어갈 위치를 찾고, 데이터가 자신보다 크다면 데이터를 오른쪽으로 이동시킨 후 해당 자리에 들어간다.

• In-place Sorting(제자리 정렬)
• Stable Sorting(안정 정렬)

삽입 정렬 과정

정렬과정

1. 첫번째 인덱스의 값은 현재 상태에서 정렬되어 있다.
2. 두번째 인덱스의 값이 들어갈 위치를 찾기 위해 저장할 데이터의 값을 미리 복사해놓는다.
3. 저장할 데이터의 값을 이미 정렬된 곳에서 차례대로 비교하며 들어갈 자리를 찾는다.
4. 자신이 들어갈 자리를 찾았으면(정렬이 필요할 때) 비교되고 있는 인덱스부터 오른쪽으로 한칸씩 이동시킨다.
5. 이후 해당 인덱스에 저장할 데이터를 저장한다.

이 과정을 코드로 나타내면

void insertion(int arr[], int n) {
	int data;
	int i, j;
	for (i = 1; i < n; i++) {
		data = arr[i];
		for (j = i - 1; j >= 0; j--) {
			if (data < arr[j]) 
				arr[j + 1] = arr[j];
			else
				break;
		}
		arr[j + 1] = data;
	}
}

 

삽입 정렬은 이미 정렬된 데이터들이 들어간 경우 O(n)의 시간 복잡도를 가지게 되면서 버블정렬, 선택정렬보다 더 빠르다.

 

 

---

Stable Sorting

중복된 데이터를 순서대로 정렬

• Bubble
• Insertion
• Merge
• Counting

unstable Sorting

중복된 데이터의 순서와 상관없이 정렬

• Selection
• Heap
• Shell
• Quick

참고하면 좋은 사이트

거품 정렬(Bubble Sort) | 👨🏻‍💻 Tech Interview