자료의 정렬과 탐색 - 2. 자료의 정렬(2)

삽입 정렬

삽입 정렬(insertion sort)는 리스트에 원소를 하나씩 삽입하는 과정을 반복해 정렬을 수행하는 알고리즘입니다. 선택 정렬 처럼 리스트의 앞쪽부터 정렬되며 삽입의 원리는 일상생활 속에서도 쉽게 발견할 수 있는데, 과제등을 학번순으로 정렬할때 순서에 맞게 중간에 끼워가는 식으로 정렬하는 것이 일반적이기 때문입니다.

//삽입정렬
#include <stdio.h>

main()
{
	int j, i, k, key;
	int a[10];
	j = -1;
	
	do {
		j++;
		scanf("%d", &a[j]);
	} while( j<9 );  //do~while 을 이용해 배열에 10개의 숫자를 입력받는다.
	for(i = 1; i<=9; i++) {
		key = a[i];
		for(k = i-1; k >= 0; k--) {
			if(a[k] > key){
				a[k + 1] = a[k];
			}
			else{
				break;
			}
		}
		a[k + 1] = key; 
	}
	for(i = 0; i <= 9; i++){ //배열에 저장된 10개의 수를 모두 출력
		printf("%d ", a[i]); 
	}
}
			

//입력:
1 3 5 7 9 2 4 6 8 10
//출력:
1 2 3 4 5 6 7 8 9 10

퀵 정렬

퀵 정렬(Quick sort)는 찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)가 개발한 정렬 알고리즘으로, 주어진 배열의 원소 중 하나를 피벗(기준값)으로 선택하여 이 원소와의 크기 비교를 통해 나머지 원소들을 분할하는 과정을 재귀적으로 수행하는 정렬 알고리즘 입니다. 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 가장 빠른 알고리즘 이라는 것이 증명되었습니다.