[알고리즘 개념] 정렬 알고리즘

developer_jennifer·2023년 4월 10일

알고리즘 알고리즘 1주차 정렬 크래프톤 정글

알고리즘

목록 보기

6/30

정렬

: 데이터 집합을 일정한 순서로 바꾸어 늘어놓은 작업

오름차순 : 값이 작은 데이터 순으로 정렬
내림차순 : 값이 큰 데이터 순으로 정렬

stable한 알고리즘
값이 같은 원소의 순서가 정렬한 후에도 유지되는 알고리즘

0. 시간 복잡도 정리

o(n**2)
- 버블 정렬
- 선택 정렬
- 삽입 정렬
o(n*logn)
- 합병 정렬
- 퀵 정렬
- 힙 정렬

1. 선택 정렬

가장 작은 원소부터 선택해 알맞은 위치로 옮기는 알고리즘

서로 이웃하지 않는 떨어져 있는 원소를 교환하므로 안정적이지 않다.
ex) 값이 같은 원소가 여러개 있을 경우

2. 삽입 정렬

주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘

#단순 삽입 정렬 알고리즘
def insertion_sort(a:MutableSequence)->None:
    n=len(a)
    for i in range(1,n):
        j=i
        tmp = a[i]
        while j>0 and a[j-1]>tmp:
            a[j]==a[j-1]
            j-=1
        a[j]=tmp

1-1. 이진 삽입 정렬

#이진 삽입 정렬 알고리즘
def binary_insertion_sort(a:MutableSequence)->None:
    n=len(a)
    for i in range(1,n):
        key=a[i]
        pl = 0
        pr = i-1
        
        while True:
            pc = (pl + pr) //2
            if a[pc]==key:
                break
            elif a[pc]<key:
                pl = pc+1
            else:
                pr=pc-1
            if pl >pr:
                break
        pd = pc +1 if pl <= pr else pr+1
        
        for j in range(1,pd,-1):
            a[j] = a[j-1]
        a[pd]=key

def binary_insertion_sort(a:MutableSequence)->None:
    for i in range(1,len(a)):
        bisect.insort(a,a.pop(i),0,i)

a안에 x와 같은 값을 갖는 원소가 여러개 있으면 가장 오른쪽 위치에 삽입

3. 셀 정렬

단순 삽입 정렬의 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘

def shell_sort(a:MutableSequence)-> None:
    n = len(a)
    h= n//2
    while h>0:
        for i in range(h,n):
            j=i-h
            tmp = a[i]
            while j>=0 and a[j]>tmp:
                a[j+h]=a[j]
                j-=h
            a[j+h]=tmp
        h//=2

4. 퀵 정렬

가장 빠른 정렬 알고리즘

과정 설명

리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
리스트의 크기가 0이나 1이 될 때까지 반복한다.

퀵정렬은 원소 수가 적은 경우에는 빠른 알고리즘이 아닌 것으로 알려져 있다.
따라서 원소수가 9개 미만인 경우 단순 삽입 정렬로 전환하고
피벗 선택은 배열의 맨 앞 원소, 맨 끝 원소를 정렬한 뒤 가운데 원소와 맨끝에서 두번째 원소를 교환하는 방법으로 선택한다.

def q_sort(list1,left,right):
    pl=left
    pr=right
    x = list1[(left+right)//2]
    
    while pl<=pr:
        while list1[pl]<x:
            pl+=1
        while list1[pr]>x:
            pr-=1
        if pl<=pr:
            list1[pl],list1[pr]=list1[pr],list1[pl]
            pl+=1
            pr-=1
        
        if left<pr:
            q_sort(list1,left,pr)
        if pl < right:
            q_sort(list1,pl,right)
    
list1=[3,1,2,5,3,1]
q_sort(list1,0,len(list1)-1)
print(list1)

5. 병합 정렬

import sys
    
def sort(list1):
    if len(list1)<2:
        return list1
    mid = len(list1)//2
    left = sort(list1[:mid])
    right = sort(list1[mid:])
    
    return merge(left,right)

def merge(left,right):
    a=0 #left
    b=0#right
    new_list=[]
    while a<len(left) and b<len(right):
        if left[a]<right[b]:
            new_list.append(left[a])
            a+=1
        elif left[a]>right[b]:
            new_list.append(right[b])
            b+=1
    while a<len(left):
        new_list.append(left[a])
        a+=1
    while b<len(right):
        new_list.append(right[b])
        b+=1  
    return new_list
    
n = int(sys.stdin.readline())
list1=[]
for i in range(n):
    number= int(input())
    list1.append(number)
for j in sort(list1):
    print(j)

6. 버블 정렬

두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘

def bubble_sort(a:MutableSequence)->None:
    n=len(a)
    for i in range(n-1):
        for j in range(n-1,i,-1):
            if a[j-1] > a[j]:
                a[j-1],a[j] = a[j],a[j-1]

6-1. 개선된 버블 정렬 1

#개선된 버블 정렬- 교환된 횟수에 따라 중단 방식 적용
def bubble_sort(a:MutableSequence) -> None:
    n=len(a)
    for i in range(n-1):
        exchng = 0
        for j in range(n-1,i,-1):
            if a[j-1]>a[j]:
                a[j-1],a[j]=a[j],a[j-1]
                exchng+=1
        if exchng == 0:
            break

exchng가 0일 경우 순차적으로 정렬되어 있는 것이므로 반복문을 종료해 준다. 교환 횟수에 따라 중단 방식을 적용하면 실행시간을 단축시킬 수 있다.

6-2. 개선된 버블 정렬 2

#개선된 버블정렬 - 이미 정렬된 원소를 제외한 나머지만 비교
def bubble_sort(a:MutableSequence)-> None:
    n=len(a)
    k=0
    while k < n-1:
        last = n-1
        for j in range(n-1,k,-1):
            if a[j-1] > a[j]:
                a[j-1],a[j]=a[j],a[j-1]
                last=j
        k= last

앞서 정렬된 배열은 제외하고 나머지만 버블 정렬하도록 하는 알고리즘이다.

6-3. 셰이커 정렬

#셰이커 정렬 - 맨뒤에서 맨앞으로 스캔했다가 다시 뒤로 스캔
def shaker_sort(a:MutableSequence) -> None:
    left = 0
    right = len(a)-1
    last= right
    while left < right:
        for j in range(right,left,-1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j],a[j-1]
                last=j
        left = last
        
        for j in range(left, right):
            if a[j] > a[j+1]:
                a[j],a[j+1] = a[j+1],a[j]
                last = j
        right = last