알고리즘 [Algorithm] - 정렬의 개요와 선택 정렬 Selection Sort (1) (C,Python)

정렬의 개요

알고리즘을 배울 때 가장 먼저 나오는 내용이 '정렬 (Sort)'이다. 그 이유는 정렬만큼 알고리즘의 효율성 차이를 극명하게 보여주는 것이 없기 때문이다!

 

 

선택 정렬

---

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

1 10 5 8 7 6 4 3 2 9

---

  일반적으로 인간은 '그냥 작은수부터 쓰면 되지'라고 생각하지만, 컴퓨터는 그렇지 않고 과정을 구체적으로 명시해줘야 한다. 위의 수를 정렬하기 위한 아이디어중 하나가 선택정렬이다.

  선택정렬이란 가장 작은 것을 선택해서 제일 앞으로 보내는 방법이다. 이는 가장 원시적이고 기초적인 방법중 하나이다.

 

C 언어

#include <stdio.h>

int main(void){  
 // 선택정렬
	int i, j, min, index, temp;
	int array[10] = { 1,10,5,8,7,6,4,3,2,9 };
	for (i = 0; i < 10; i++) { //배열의 원소 하나씩 선택하며 반복
		min = array[i]; // 반복문이 실행될 때의 맨 첫째 값으로 min, index 초기화
		index = i;
		for (j = i; j < 10; j++) { // 정렬 안된 부분만 반복
			if (min > array[j]) { //만약 최솟값이 현재 값보다 크다면
				min = array[j]; // min값 업데이트
					index = j;
			}
		}
			temp = array[i]; // 모든 정렬 안된 곳 순환후 스왑
			array[i] = array[index];
			array[index] = temp;
	}

	for (i = 0; i < 10; i++) { //배열 출력
		printf("%d ", array[i]);
	}
	return 0;
  }

 

이 방식은 데이터의 갯수가 N개일 때 비교연산을 N * (N+1) / 2 번 수행한다.

  따라서 선택 정렬의 시간 복잡도는 O(N^2)이다.

 

따라서 데이터의 갯수가 10,000개라면 대략 1억번의 비교연산을 수행하게 된다.

 

 

 

 

 

 

 

파이썬

a = [1,10,5,8,7,6,4,3,2,9]

for i in range(len(a)): # 앞에서 부터 한개씩
  min = a[i] # 맨 첫번째 값을 최솟값으로 초기화
  idx=i # idx저장
  for j in range(len(a)-i): # i번째 부터 순회
    if min> a[j+i]: # 만약 min 값이 j-i보다 크면
      min = a[j+i] # min에 a[j-i]저장
      idx = j+i #min idx저장
  tmp = a[i]
  a[i] = min
  a[idx] = tmp

a

 

---

이 글은 나동빈님의 실전 알고리즘 강좌 (Algorithm Programming Tutorial)를 참고해 작성하였습니다.

https://www.youtube.com/watch?v=qQ5iLNjpxSk&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz