이번 포스트에서는 정렬에 대해 간단히 소개해보고자 한다.
이전 포스트(이진탐색)에서 언급했던 전제조건인 '정렬 완료된 데이터'를 만들기 위한
데이터를 정렬하기 위한 방법 몇 가지를 정리한다.

거품정렬(Bubblesort)

정렬되는 원소의 이동이 마치 수면 위로 올라오는 거품과 같은 모습에서 이름 붙여진 거품정렬은
인접한 두 원소를 비교하여 정렬되어 있다면 통과, 그렇지 않다면 교환하는 방식으로 진행한다.

아래의 그림에서 j는 처음부터 i까지 데이터 요소의 정렬을 진행하며 j가 i번째까지 간다면
다시 처음으로 돌아오며, i는 한 칸 왼쪽으로 진행한다.
i가 처음이 될 때까지 반복하면 정렬이 완료된다.

장점

• 코드가 단순하고 구현이 쉽다.

단점

• 정렬 시간동안 인접한 두 원소에 매 번 접근하여 정렬조건을 비교하므로 데이터가 늘어날수록 시간이 급격하게 늘어난다.
  
  

코드

void bubbleSort(int * array,int lengthOfArray) {
	int temp;
	for (int i = lengthOfArray - 1; i > 0; i--) {
		for (int j = 0; j < i;j++) {//Send the max value to the end of the array
			if (array[j]>array[j+1]) {
				temp = array[j];
				array[j] = array[j+1];
				array[j+1] = temp;
			}
		}
	}
}

선택정렬

데이터의 전체에서 최솟값을 찾아 정렬 안 된 데이터의 처음과 교환해주는 선택정렬은 아래와 같은 순서로 진행된다.

• 주어진 데이터에서 최솟값을 찾는다
• 그 값을 맨 앞에 위치한 값과 교환(맨 앞의 값이 최소일 경우 통과)
• 맨 처음 위치를 제외한 나머지 데이터에 대해 위의 두 과정을 반복

장점

• 최대 교환 횟수가 정해져있다.
• 코드가 단순하다.

단점

• 같은 값의 자료가 있을 때 순서가 바뀌는 경우가 있다.

코드

void selectionSort(int * array,int lengthOfArray) {
	int temp = 0;
	int min;
	for (int i = 0; i < lengthOfArray-1;i++) {
		min = i;
		for (int j = i + 1; j < lengthOfArray;j++) {
			if (array[j] < array[min])
				min = j;
		}
		if (i != min) {
			temp = array[i];
			array[i] = array[min];
			array[min] = temp;
		}
	}
}

---

References

• 위키백과 - 버블정렬 , 선택정렬
• Do it! 자료구조와 함께 배우는 알고리즘 입문(한빛미디어)
• https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html
• https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html