[자료구조] 정렬

정렬

• 대상을 크기순으로 오름차순이나 내림차순으로 나열하는 

 

 

선택 정렬 알고리즘

selection_sort(A, n):

for i <- 0 to n - 2 do
	least <- A[i], A[i+1],..., A[n-1] 중에서 가장 작은 값의 인덱스;
    A[i]와 A[least]의 교환;
    i++;

 

 

 

삽입 정렬 알고리즘

insertion_sort(A, n):

for i <- 1 to n - 1 do
	key <- A[i]
    j <- i - 1;
    while j >= 0 and A[j] > key do
    	A[j + 1] <- A[j];
        j <- j - 1;
	A[j + 1] <- key

 

 

 

버블 정렬 알고리즘

BubbleSort(A, n):

for i<- n 0 1to 1 do
	for j <- 0 to i - 1  do
    	j와 j+1번째의 요소가 크기순이 아니면 교환
        j++;
	i--;

 

 

 

합병 정렬 알고리즘

merge_sort(list, left, right):

if left < right
	mid = (left + right) / 2;
    merge_sort(list, left, mid);
    merge_sort(list, mid + 1, right);
    merge(list, left, mid, right);

 

merge(list, left, mid, last):

i <- left
j <- mid + 1;
k <- left;
sorted 배열을 생성;
while i <= mid and j <= right do
	if(list[i] < list[j])
    	then
        	sorted[k] <- list[i];
            k++;
            i++;
		else
        	sorted[k] <- list[j];
            k++;
            j++;

 

 

 

기수 정렬 알고리즘

RadixSort(list, n):

for d <- LSD의 위치 to MSD의 위치 do
{
	d번째 자릿수에 따라 0번부터 9번 버킷에 집어놓는다.
    버킷에서 숫자들을 순차적으로 읽어서 하나의 리스트로 합친다.
    d++;
}