[Algorithm] sort(정렬 알고리즘)

정렬(sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등으로 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘으로 데이터를 정렬하면 이진탐색(binary search)가 가능해진다. 

파이썬에서 버블정렬, 선택정렬 알고리즘을 사용하는 것보다 sort()함수와 sorted()함수가 O(NlogN)의 시간 복잡도를 보장해주기 때문에 더 효율적이지만, 간혹 수기로 코딩테스트를 보거나 직접 정렬 알고리즘을 아는지 물어보는 경우가 있기 때문에 알고 있는 것이 좋다

1. 선택 정렬(selection sorting)

컴퓨터가 데이터를 정렬할 떄 어떻게 할 지 한번 생각해보자 데이터가 무작위로 여러개 있을 때 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다면 선택 정렬을 할 수 있다.

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)) :
  min_idx = i
  for j in range(i + 1, len(array)) :
    if array[min_idx] > array[j] :
      min_idx = j
  array[i],array[min_idx] = array[min_idx],array[i]

print(array)

2. 삽입 정렬(insertion sorting)

삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬이라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 삽입 정렬은 두 번째 데이터로부터 시작한다. 왜냐하면 첫 번째 데이터는 그자체로 정렬되어 있다고 판단하기 때문이다.

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1,len(array)) :
  for j in range(i,0,-1) :
    if array[j] < array[j-1] :
      array[j] , array[j-1] = array[j-1] , array[j]
    else :
      break
print(array)

3.  퀵 정렬 (quick sort)

퀵 소트(Quick Sort)는 가장 널리 사용되는 정렬 알고리즘 중 하나이다. 퀵 소트는 분할 정복(Divide and Conquer) 방법을 기반으로 하며, 시간복잡도는 O(NlogN)으로 효율적이다

퀵 소트는 분할 , 정복, 결합의 과정으로 이루어 진다. 

위의 과정을 재귀적으로 반복하면서, 부분 배열의 크기가 1로  충분히 작아질 때까지 반복한다. 일반적으로 퀵 소트는 재귀 호출을 통해 정렬을 수행하며, 원소의 개수가 적어질수록 더욱 효율적인 정렬이 이루어진다.

# quick sort
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]

def quick_sort(array) :
	if len(array) <= 1 :			# 길이가 1보다 작거나 같으면 배열 출력
    	return array
    
    else :
    	pivot = array[0]			# 1 번째 원소를 pivot으로 설정
        tail = array[1:]			# 1 번째 원소를 제외한 나머지 원소를 tail로 설정
        
        left_side = [x for x in tail if x <= pivot]				# pivot을 기준으로 왼쪽으로 분할
        right_side = [x for x in tail if x > pivot]				# pivot을 기준으로 오른쪽으로 분할
        
        return quick_sort(left_side) + [pivot] + quick_sort(right_side)			# 병합(정복)
        

print(quick_sort(array))

4.  계수 정렬 (count sort) 

계수 정렬은 특정한 조건이 부합할 때만 사용이 가능하다 . 여기서 특정한 조건은 알고리즘 사용자가 배열의 크기를 알아야 한다는 것이다. 데이터 개수가 N , 데이터 최댓값이 K라고 가정할 때, 계수 정렬은 시간복잡도 O(N)을 보장한다. 하지만 계수 정렬은 데이터의 크기 범위가 제한 되어 정수 형태로 표현 할 수 있을 때만 사용할 수 있다. 

 

# count sort
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]			
count = [0] * (max(array) + 1)			# max(array) + 1의 크기의 배열 생성

for i in range(len(array)) :			
  count[array[i]] += 1					# 배열의 원소 인덱스 위치에 하나씩 옮겨 담는다

for i in range(len(count)) :			# 리스트에 기록된 정렬 정보 확인
  for j in range(count[i]) :			
    print(i,end="")						# 출력 
    --------------------------------------------------------------------------------------
   
    # 계수 정렬(함수)
    def counting_sort(arr):
    if not arr:							# 빈 배열
        return arr
    max_val = max(arr)					# 리스트 내 가장 큰 수를 기반으로 리스트의 크기를 정의
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1					# 리스트 내 원소 빈도 수 기록 		
    result = []
    for i, c in enumerate(count):		# i : 인덱스 . c : 개수 
        result.extend([i] * c)
    return result

GPT )

예시

주어진 배열이 [4, 2, 2, 8, 3, 3, 1]인 경우:

1. 최댓값은 8입니다.
2. 카운트 배열은 [0, 0, 0, 0, 0, 0, 0, 0, 0]에서 시작합니다.
3. 배열의 값에 따라 카운트 배열이 업데이트됩니다:
   • count[4]가 1로, count[2]가 2로, count[8]가 1로, count[3]가 2로 증가합니다.
4. 최종 카운트 배열은 [0, 1, 2, 2, 1, 0, 0, 0, 1]입니다.
5. 결과 배열은 [1, 2, 2, 3, 3, 4, 8]가 됩니다.

계수 정렬의 시간 복잡도는 O(n + k)로, 여기서 n은 배열의 길이, k는 배열에서 가장 큰 값입니다. 메모리 복잡도는 O(k)입니다. 이 알고리즘은 데이터의 범위가 상대적으로 작고, 데이터가 정수일 때 매우 효율적입니다.

 

※ lambda를 사용한 정렬

2차원 이상의 다중 배열을 특정 원소에 정렬해야되는 경우가 종종 있다. 예를 들면 ,

N 명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.

입력조건)
첫번째 줄에 학생의 수 N이 주어진다.
두번째 줄 부터 N+1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 성적은 100이하의 자연수이다

input )
2
홍길동 95
이순신 77

output )
이순신 홍길동

정답)

n = int(input())
arr =  []

for _ in range(n) :
  arr.append(tuple(input().split()))

arr = sorted(arr,key = lambda x : x[1])

for i in arr :
  print(i[0],end=" ")

ex)baekjoon-1931

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

import sys
input = sys.stdin.readline
N = int(input())
lesson = []
cnt = 0 
for _ in range(N) :
  lesson.append(tuple(map(int,input().split())))
lesson = sorted(lesson,key = lambda x : (x[1],x[0]))
t = 0
for start,end in lesson:
  if t <= start :
    cnt += 1
    t = end 
print(cnt)

 

참고 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 )

https://github.com/ndb796/python-for-coding-test

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

2023 한권으로 합격하는 취업 코딩테스트)

https://product.kyobobook.co.kr/detail/S000201209716

2023 한권으로 합격하는 취업 코딩테스트 | 컴공선배 - 교보문고