Bubble sort, Insertion sort, Selection sort

---

Bubble Sorting Algorithm

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.

알고리즘의 흐름을 보면 이중 반복문을 통해 안쪽 반복문을 이용하여 0번 인덱스와 1번 인덱스를 비교하고 1번 인덱스와 2번 인덱스를 비교하는 방식으로 i번째 인덱스와 i+1번째 인덱스를 비교한다. 다음으로 바깥 반복문을 수행하려고 보면 마지막 인덱스에는 가장 큰 자료가 도달해있다. 그러면 마지막 인덱스를 제외하고 n-1번째까지 반복문을 진행하면 n-1번째 인덱스에 두번째로 큰 자료가 도착을한다. 따라서 바깥반복문은 j<n-(i+1)까지 반복문을 진행한다.

void bubblesort(int N, keytype data[]) {
{
	int i, j, temp;

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

Time complexity

Tn = (n-1)+(n-2)+....+3+2+1

따라서 big-O notation으로 표현하면 O(n^2)이다.

---

Insertion Sorting Algorithm

매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아서 그 위치에 넣는 알고리즘이다.

알고리즘의 흐름을 보면 두번째 자료부터 조사가 시작이 된다. 조사중인 자료보다 앞쪽의 자료들과 비교를 하여 들어갈 수 있는 위치에 넣어주는 것이다.

void insertionsort(int n, keytype S[])
{
	index i,j;
    keytype x;
    
    for (i=1; i<n; i++) {
    	x = S[i];
        j = i - 1;
        while (j>=0 && S[j] > x) {
        	S[j+1] = S[j];
            j--;
        }
        S[j+1] = x;
    }
}

Time complexity

worst-case: 주어진 i에 대해 최대 i-1번의 비교가 이루어진다.

average-case: 주어진 i에 대해, x가 삽입될 수 있는 장소는 i곳이 있다.

따라서 평균 비교 횟수는 아래와 같이 된다.

---

Selection Sorting Algorithm

in-place sorting 알고리즘중 하나로 원소를 넣을 위치를 정해두고 해당 위치에 넣을 원소를 찾는 알고리즘이다.

알고리즘의 흐름은 첫번째 자료부터 마지막 자료까지 조사를 하여 최소값을 찾아서 첫번째 위치에 넣어두고 두번쨰 자료부터 마지막 자료까지 조사를 하여 최소값을 찾아서 두번째 위치에 넣는 것을 마지막에서 두번째까지 반복하는 알고리즘이다.

void selectionsort(int n, keytype S[])
{
	index i,j,smallest;
    
    for (i=0; i<n-1; i++) {
    	smallest = i;
        for (j=i+1; j<n; j++){
        	if (S[j] < S[smallest])
            	smallest = j;
        exchange S[i] and S[smallest];
    }
}

Time compexity

 

worst-case

따라서 big-O notation으로 표현해보면 O(n^2)이다.

---