정렬 알고리즘

여러 개의 데이터를 특정 순서로 나열하는 조작을 정렬이라고 부른다.

 

Ex) [2, 3, 1, 4] 를 오름차순으로 정렬하면 [1, 2, 3, 4] 이 된다.

 

정렬은 자주 쓰이기 때문에 여러 프로그래밍 언어에서 표준 라이브러리로 제공한다.

파이썬의 경우는 A.sort()의 형태로, C++에선 sort(A+1, A+N+1)의 형태로, C#에서는 Array.Sort(A)의 형태로 배열 A를 오름차순으로 정렬할 수 있다.

---

예제를 풀어보자.

오름차순 정렬 문제(백준 2750번_수 정렬하기) https://www.acmicpc.net/problem/2750

Python

import sys
input = sys.stdin.readline

N = int(input())
li = [int(input()) for _ in range(N)]

li.sort()
print(*li, sep = '\n')

 

C++

#include<cstdio>
main ()
{ 
int n, v, i, a[2001]={0};  
scanf ("%d", &n); 
while (n--)
    scanf ("%d", &v), a[v+1000] = 1;
for (i = 0; i < 2001; ++i)
    if (a[i])
      printf ("%d\n", i-1000);
}

C#

static void Main()
{
    int N = int.Parse(Console.ReadLine());
    int[] nums = new int[N];
    for (int i = 0; i < N; i++)
    {
        nums[i] = int.Parse(Console.ReadLine());
    }
    Array.Sort(nums);
    for (int i = 0; i < nums.Length; i++)
    {
        Console.WriteLine(nums[i]);
    }
}

---

정렬 알고리즘 종류는 다음과 같다.

정렬 알고리즘

• 선택정렬

선택정렬

1번 부터 훑어서 제일 작은걸 1번에 배치. 그 후 남은 것들 중 제일 작은걸 그 다음에 배치.. 이를 반복.

 

• 삽입정렬

삽입정렬

k번째 원소를 1부터 k-1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식.

 

• 버블정렬

버블정렬

거품이 수면으로 올라오는 듯한 모습을 보이기 대문에 지어진 이름. 1번부터 시작하며, k와 k+1을 비교해서 k보다 k+1이 작으면 서로 순서를 바꾸고 아닌경우엔 순서를 유지한다. 이를 반복.

 

• 병합정렬

병합정렬

배열의 길이가 1이 될 때까지 2개의 부분 배열로 분할. 그 후, 2개의 부분 배열을 합병하고 정렬한다.

이를 모든 부분 배열이 합병될 때까지 반복한다.

 

• 힙정렬

힙정렬

N개의 노드에 대한 완전이진트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다. 

최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다. 반복한다.

 

• 퀵정렬

퀵정렬

리스트 중 하나를 고르고, 기준 값보다 큰 수들은 모두 기준값보다 뒤에 놓게 된다. 한번 기준값으로 정해진 수는 정렬후 위치가 바뀌지 않는다.

 

	선택정렬	삽입정렬	버블정렬	병합정렬	힙정렬	퀵정렬
시간복잡도	n^2	n^2	n^2	nlogn	nlogn	nlogn