[Algorithm] 정렬 - 선택정렬

김상웅·2022년 7월 4일
0

[알고리즘]

목록 보기
16/18

✅ 선택정렬


선택 정렬은 정렬되지 않은 데이터 중 가장 작은 데이터를 선택해서 맨 앞에서부터 순서대로 정렬해나가는 알고리즘을 의미합니다.

전체 데이터에서 매번 가장 작거나 큰 데이터를 선택하여 데이터 간의 위치를 변경하는 과정을 반복합니다.

그 과정을 반복하여 데이터를 오름차순 또는 내림차순으로 정렬할 때 사용합니다.


선택 정렬의 종류는 앞서 언급한 바와 같이 2가지로 나눌 수 있습니다.

  • 최소 선택 정렬 : 가장 작은 데이터를 맨 앞에서부터 오름차순으로 정렬
  • 최대 선택 정렬 : 가장 큰 데이터를 맨 앞에서부터 내림차순으로 정렬

동작 과정은 다음과 같습니다.

  1. 전체 데이터에서 가장 작은(큰) 데이터를 선택하고 맨 앞에 있는 데이터와 자리를 바꿉니다.
  2. 그 다음 가장 작은(큰) 데이터를 선택하고 그 다음 위치의 데이터와 자리를 바꿉니다.
  3. 위 과정을 반복합니다.

하지만, 다음 설명을 한번 같이 볼까요.

It has O(n2) time complexity, making it inefficient on large lists,
and generally performs worse than the similar insertion sort.
Selection sort is noted for its simplicity,
and it has performance advantages over more complicated algorithms
in certain situations, particularly where auxiliary memory is limited.

선택정렬은 메모리가 제한되어 있거나 특정 상황에서 더 복잡한 알고리즘을 사용할 때보다 성능적으로 효율적일 수 있으나,
리스트의 크기가 크거나 삽입 정렬에 비해 비효율적인 문제점이 있다고 말합니다.



✅ 문제


선택정렬을 좀 더 쉽게 이해하기 위해 문제를 통해 알아보겠습니다.

nums라는 정렬되지 않은 숫자 배열을 인자로 받습니다.

오름차순으로 정렬된 배열을 반환하는 프로그램을 작성해주세요.

예시:

input = [5, 1, 3]
output = [1, 3, 5]


📌 풀이


선택 정렬을 활용한 풀이는 다음과 같습니다.

#1 각 원소를 선택하기 위해 첫번째 반복문을 사용합니다.

#2 각 원소 이후의 값 중 가장 작은 수를 찾기 위해 두번째 반복문을 사용합니다.

#3 두 수의 크기 비교를 하여 더 작은 수가 뒤에 있다면 두 수의 위치를 바꾸어줍니다.

코드를 통해 알아보겠습니다.

def answer(nums) :
	#1
	for i in range(len(nums)):
    	
        #2
    	for j in range(len(nums)):
        	#3
        	if nums[i] > nums[j] :
            	temp = nums[i]
                nums[i] = nums[j]
                nums[j] = temp
                
    return nums

#3은 다음과 같은 표현식으로 바꿔 사용할 수 있습니다.

nums[i], nums[j] = nums[j], nums[i]
profile
누구나 이해할 수 있도록

0개의 댓글