정렬 - 버블정렬, 선택정렬, 삽입정렬, 퀵정렬

정렬이란

정렬이란 데이터를 순서대로 나열하는 방법을 의미한다. 이진 탐색을 가능하게도 하고, 데이터를 조금 더 효율적으로 탐색할 수 있게 만든다. 효과적으로 정렬하는 다양한 알고리즘이 존재하므로, 각 알고리즘의 내용을 알고 적절히 구현하는 능력은 개발자로서 중요하다.

버블 정렬

설명

버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를 ... 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식이다.

교환 과정을 한바퀴 돔으로써 가장 큰 숫자를 마지막에 위치할 수 있으므로, 교환 과정을 n-1  바퀴 진행하면 된다.

구현

def bubblesort(lst):
    # 최댓값을 구하는 알고리즘을 len(lst) - 1 만큼 반복한다.
    for i in range(len(lst)-1):
        # 이미 구한 최댓값은 범위에서 제외한다.
        for cur in range(len(lst) - 1 - i):
            if lst[cur] > lst[cur + 1]:
                lst[cur], lst[cur + 1] = lst[cur + 1], lst[cur]
    return lst

선택정렬

설명

선택정렬은 모든 숫자에서 가장 작은 숫자를 앞에 두고, 그 다음 숫자들에서 그 앞에 두고... n-1 반복하는 방법이다.

구현

def selectionsort(lst):
    for i in range(len(lst) - 1):
    	# min은 최솟값의 인덱스 값. 처음엔 i로 가정
        min = i
        for cur in range(i + 1, len(lst)):
            if lst[cur] < lst[minimun]:
                min = cur

        if min != i:
        	# i와 최솟값의 위치를 변경
            lst[min], lst[i] = lst[i], lst[min]

    return lst

삽입 정렬

설명

삽입 정렬을 전체에서 하나씩 올바른 위치에 삽입하는 방식이다. 즉, 정렬된 데이터를 사이에 하나를 위치에 맞게 삽입하는 것이다.

구현

def insertionsort(lst):
    for i in range(len(lst)-1):
        for j in reversed(range(1, i+2)):
            # 새로 들어온 숫자 i+1 을 인덱스 1-1까지 비교 및 교환 
            if lst[j-1] > lst[j]:
                lst[j-1], lst[j] = lst[j], lst[j-1]
            else:
                break
    return lst

퀵 정렬

설명

퀵 정렬은 분할 정복(Divide and Conquer)을 통해 주어진 배열을 정렬하는 알고리즘이다.

배열에서 기준(pivot)을 잡고, 기준보다 값이 작은 집합과 큰 집합으로 나눈다. (Divide)

그리고 그 사이에 기준을 위치시킨다.

작은 집합과 큰 집합을 대상으로 재귀호출하여 정렬한 뒤(Conquer) 결과를 합치면 정렬된 배열을 얻을 수 있다.

구현

#i와 j가 무엇을 의미하는지 파악하는 게 중요하다!
def quicksort(lst, start, end):
    def partition(part, ps, pe):
        #pivot을 맨 뒤 인덱스로 설정
        pivot = part[pe]
        #초기 i는 -1로 설정(최종적으로 i+1이 pivot의 위치) 
        i = ps - 1
        for j in range(ps, pe):
            if part[j] <= pivot:
                #pivot보다 작으면 위치 이동
                i+=1
                part[i], part[j] = part[j], part[i]

            #pivot 위치 고정
            part[i+1], part[pe] = part[pe], part[i+1]
            #pivot 위치 반환
            return i+1

    p = partition(lst, start, end)
    quicksort(lst, start, p-1)
    quicksort(lst, p+1, end)
    return lst

문제) 배열 합치기와 정렬

# 정렬 알고리즘 - 퀵정렬
arr1 = list(map(int,input().split(" ")))
arr2 = list(map(int,input().split(" ")))
arr = arr1 + arr2

def quicksort(arr,start,end):
    def partition(part,ps,pe):
        pivot = part[pe]
        i = ps - 1
        for j in range(ps,pe):
            if part[j]<=pivot:
                i+=1
                part[j],part[i]=part[i],part[j]
        part[i+1], part[pe] = part[pe], part[i+1]
        return i+1

    #종료 조건
    if start >= end:
        return None

    p = partition(arr,start,end)
    quicksort(arr,start,p-1)
    quicksort(arr,p+1,end)

quicksort(arr,0,len(arr)-1)
print(arr)

문제) 회의실 배정 최적화

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

설명

회의를 최대한 많이 하려면? 일찍 끝나야 다음 회의를 시작할 수 있으므로 다음과 같은 방법으로 진행한다. 

• 회의가 끝나는 시간 기준으로 오름차순 정렬한다.
• 회의가 끝나는 시간이 같은 것이 있다면 일찍 시작하는 것 순으로 정렬한다.
  • (2,2), (1,2) 가 주어졌을 때, output이 2가 나와야하므로
• 이전 회의가 끝나는 시간 다음에 시작하는 회의를 고른다.

구현

n = int(input())
meetings = []
answers = []
for _ in range(n):
    meeting = list(map(int,input().split(" ")))
    meetings.append(meeting)

def quicksort(meetings,start,end):
    def partition(part,ps,pe):
        i = ps - 1
        pivot = part[pe][1]
        for j in range(ps,pe):
            if part[j][1]<=pivot:
                i+=1
                part[j],part[i]=part[i],part[j]
        part[i+1],part[pe]=part[pe],part[i+1]
        return i+1
    
    if start>=end: return 

    p = partition(meetings,start,end)
    quicksort(meetings,start,p-1)
    quicksort(meetings,p+1,end)

quicksort(meetings,0,len(meetings)-1)

for i in range(len(meetings)-1):
    for j in range(len(meetings)-i-1):
        if meetings[j][1]==meetings[j+1][1] and meetings[j][0]>meetings[j+1][0]:
            meetings[j],meetings[j+1]=meetings[j+1],meetings[j]

answers.append(meetings[0])

for i in range(1,len(meetings)):
    meeting = meetings[i]
    if answers[-1][1]<=meeting[0]:
        answers.append(meeting)

print(len(answers))