[기본 정렬 알고리즘] 1. 선택 정렬(Selection Sort)이란

 

 

 

1. 정렬 알고리즘이란? 

 

정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 그렇다면 왜 정렬 알고리즘을 사용해 데이터를 열거할까? 이유는 탐색하기 위해서다. 컴퓨터는 수 많은 데이터를 처리해야하는데 만약 데이터를 정렬하지 않는다면 데이터를 하나하나 일일이 탐색(순차 탐색)하여 원하는 데이터를 탐색해야 한다. 일반적으로 데이터를 삭제/삽입하기보다 탐색/조회하는 경우가 많기 때문에 매번 데이터를 탐색할 때마다 이런 식의 탐색은 매우 비효율적이다. 하지만 데이터가 일정한 규칙에 따라 순서대로 열거되었다면 다양한 탐색 방법을 이용하여 원하는 데이터를 빠르고 효율적으로 탐색할 수 있다. 

 

 

2. 선택 정렬(Selection Sort)이란? 

 

- 선택 정렬이란 배열/리스트에서 최소값을 선택하여 배열/리스트의 맨 앞에서부터 정렬시키는 방법이다. 

 

- 정렬 알고리즘 중 제자리 정렬 알고리즘 중 하나이다. 제자리 정렬 알고리즘이란 원소들의 갯수에 비해서 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘으로, 선택 정렬의 경우 입력 배열 자체를 사용하여 정렬하여 입력 배열 외에 추가적인 메모리가 필요하지 않다. 

 

- 선택 정렬 순서

 

• 주어진 배열/리스트를 한바퀴 돌며 최소값을 찾는다.
• 찾은 최소값을 맨 앞에 위치한 값과 교체한다
• 맨 처음 위치를 빼고 나머지 배열/리스트를 위와 같은 방법으로 교체한다.  

  

- 선택 정렬은 정렬을 위해 비교하는 횟수는 많지만, 교환 횟수는 상당히 적다. 따라서 교환이 많이 이루어져야 하는 역순 정렬같은 자료 상태에서 효율적으로 사용할 수 있다. 

 

3. 선택 정렬의 예제 

 

 

4. 선택 정렬의 코드

 

 

public class Selection {

	public int[] sort(int[] data) {
		int min = Integer.MAX_VALUE; // 최소값 데이터 인덱스 저장 변수
		int tmp = 0 ; // 데이터 교체할 때 임시 저장 변수

		for(int i = 0 ; i < data.length; i++){

			min = i; 

			for(int j = i+1; j < data.length; j++){
				if(data[min] > data[j]) min = j; // 최소값 구하기
			}

			swap(arr, i, min);   // 최소값과 자리 교체
			
		}

		return data;
	}

	private static void swap(int[] arr, int a, int b) { 
		int tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp; 
	}
}

 

 

 

5. 선택 정렬의 복잡도 

 

 

- 공간 복잡도 

  : 별도의 추가 공간을 사용하지 않고 입력된 배열 안에서 교환을 통해 정렬이 수행되므로 O(n)의 공간 복잡도를 가진다.

 

- 시간 복잡도 

  : 총 두개의 for 루프를 이용하며 외부 루프를 통해 모든 인덱스에 접근하므로 기본적으로 O(N)의 시간 복잡도를 가진다. 이후 내부 루프를 통해 매 루프마다 최솟값을 찾고 해당 하는 자리의 데이터와 교환해야 하므로  추가적으로 O(N)의 시간이 필요하다. 그러므로 총 O(N²)의 시간 복잡도를 가진다. 

 

• 최선 시간 복잡도 : O(N²)
• 평균 시간 복잡도 : O(N²)
• 최악 시간 복잡도 : O(N²)