platinant

삽입 정렬은 앞의 두 정렬과 같이 유명한 \(\BigO{N^2}\)정렬 중 하나이다. 하지만 앞의 두 정렬과는 크게 다른 점이 있다. 앞의 두 정렬은 정렬해야 할 값들이 다 주어져야만 알고리즘을 실행할 수 있지만 삽입 정렬은 나중에 자료가 추가되어도 알고리즘을 실행할 수 있다는 것이다. 삽입 정렬은 이미 정렬된 배열에 새로운 수를 추가하고 새로 정렬된 배열을 만들어냄으로써 정렬을 한다. 새로 정렬된 배열을 만들기 위해서는 원래 배열에서 새로 들어온 수가 들어갈 위치를 찾아야 한다. 이를 위해 맨 뒤의 큰 수들부터 차례로 비교해가며 버블 정렬하듯이 두 수를 바꾸어가며 알맞은 자리를 찾아간다. 이 아이디어를 코드로 표현하면 다음과 같다. void InsertionSort(int N,int a[]){ for(..

버블 정렬은 간단한 코드 때문에 입력이 크지 않은 경우 많이 사용된다. 이 정렬 알고리즘은 첫번째부터 N번째까지 차례대로 보면서 만약 인접한 두 값이 역순일 경우 바꾼다. 이걸 N번 반복하면 수열이 정렬된다. 이것은 이 알고리즘을 한 번 실행할 때마다 가장 큰 원소가 제자리로 가기 때문에 N번 후에는 모든 수열이 정렬됨을 알 수 있기 때문이다. 이것을 코드로 구현하면 다음과 같다. void BubbleSort(int N,int a[]){ for(int i=0;i

선택 정렬은 가장 직관적인 정렬 알고리즘이다. 아마 사람들이 손으로 직접 정렬을 할 때 가장 많이 사용할 것이다. 수들을 오름차순으로 정렬한다고 해보자. 먼저 가장 작은 수를 찾아 맨 앞에 놓은 뒤 나머지 수들에서 똑같은 절차를 반복하면 정렬된 수열을 얻을 수 있다. 이같은 간단한 아이디어를 코드로 구현하면 다음과 같다. void SelectionSort(int N,int a[]){ for(int i=0;i