정렬 알고리즘(sorting algorithm) - 선택 정렬(selection sort)

정렬 알고리즘

n개의 숫자가 주어졌을때 이를 오름차순 / 내림차순으로 정렬하는 알고리즘

다양한 알고리즘이 있으며, 알고리즘에 따라 시간 복잡도가 다르다

1. 선택 정렬 (selection sort)

•정렬되지 않은 범위에서 가장 작은(또는 큰) 원소를 찾아서 맨앞(또는 맨뒤) 원소와 변경

•각 루프마다

1. 정렬되지 않은 범위에서 가장 작은(또는 큰) 원소를 찾는다

2. 찾은 원소와 맨앞(또는 맨뒤) 원소를 교환한다

3. 맨앞(또는 맨뒤) 원소를 정렬되지 않은 범위에서 제외한다

•정렬 방식

•시간 복잡도

탐색(비교)는 4, 3, 2, 1 번 실행 되었으므로

n-1, n-2, n-3, n-4 번

-> n-1, n-2, ..., 1 이라 볼수있다.

즉 총 비교 수는 (n-1) + (n-2) + ... + 1

= ( (n-1) * (n - 1 + 1) )  / 2

= ( n * (n - 1) ) / 2 

= (n^2 - n) / 2

빅오표기법으로 표기하면

O(n^2) 이 된다.

•공간 복잡도

한개의 배열 [4, 1, 7, 2, 5]만 사용하므로

n개의 원소가 들어간 배열의 경우

O(n) 이 된다.

2. 버블 정렬

•정렬되지 않은 범위의 맨 앞부터 맨 뒤까지 순차적으로 연속된 인덱스의 값을 비교하여 정한 기준에 의해 정렬하는 방식

    - 오름차순으로 정렬할 경우 연속된 인덱스의 값을 비교하여 작은 수가 앞으로, 큰 수가 뒤로 정렬

    - 내림차순으로 정렬할 경우 연속된 인덱스의 값을 비교하여 큰 수가 앞으로, 작은 수가 뒤로 정렬

•반복문의 첫 바퀴가 지나면 가장 큰/작은 수가 맨 뒤로 이동하게 된다. (오름차순의 경우 가장 큰 수, 내림차순의 경우 가장 작은 수)

•이중 반복문을 사용하게되며, 바깥의 반복문은 (n - 1)번 반복, 안쪽 반복문은 (n - 바깥 반복문의 반복된 횟수)만큼 반복한다.

•정렬 방식

•시간 복잡도

탐색(비교)는 4, 3, 2, 1 번 실행 되었으므로

n-1, n-2, n-3, n-4 번

-> n-1, n-2, ..., 1 이라 볼수있다.

즉 총 비교 수는 (n-1) + (n-2) + ... + 1

= ( (n-1) * (n - 1 + 1) )  / 2

= ( n * (n - 1) ) / 2 

= (n^2 - n) / 2

빅오표기법으로 표기하면

O(n^2) 이 된다.

•공간 복잡도

한개의 배열 [5, 7, 4, 2, 1]만 사용하므로

n개의 원소가 들어간 배열의 경우

O(n) 이 된다.