파이썬을 이용한 정렬 알고리즘

import random # random 메소드 사용을 위해 import

a = random.sample(range(1, 10), 5) # 1<= x < 11의 난수 5개 리스트로 생성
print(a)# 정렬 전 리스트
print('')
for i in range(1, len(a)): # 리스트의 크기만큼 반복
    for j in range(i, 0, -1): # j 인덱스의 값이 줄어드면서 삽입할 위치를 찾을 때까지 반복
        if a[j] < a[j-1]: # 현재 인덱스가 앞의 원소보다 작다면
            a[j], a[j-1] = a[j-1], a[j] # swap해서 값 뒤로 밀어내기
        else : break # 불필요한 반복을 피하기 위해 break
print('')
print(a)# 정렬 후 리스트 출력

#출력
[8, 9, 3, 1, 6]


[1, 3, 6, 8, 9]

import random # random 메소드 사용을 위해 import

a = random.sample(range(1, 10), 5) # 1<= x < 10의 난수 5개 리스트로 생성
print(a) # 정렬 전 리스트
print('')
for i in range(1, len(a)): # 리스트의 크기만큼 반복
    for j in range(0, len(a)-1): # 각 회전당 정렬이 끝나지 않은 친구들을 위해 반복
        if a[j] > a[j+1]: # 현재 인덱스의 값이 다음 인덱스의 값보다 크면 실행
           a[j+1], a[j] = a[j], a[j+1] # swap해서 위치 바꾸기
print('')
print(a) # 정렬 후 리스트

#출력
[4, 9, 2, 5, 7]


[2, 4, 5, 7, 9]

import random # random 메소드 사용을 위해 import

a = random.sample(range(1, 10), 5) # 1<= x < 10의 난수 5개 리스트로 생성
print(a)# 정렬 전 리스트
print('')
for i in range(len(a)-1): # 리스트의 크기-1만큼 반복
    for j in range(i+1, len(a)): # 해당 인덱스+1부터, 리스트 크기만큼 반복
        if a[i] > a[j]: # 인덱스의 값이 비교 인덱스보다 더 크다면
            a[i] , a[j]  = a[j], a[i] # swap 해주기
print('')
print(a) # 정렬 후 리스트

#출력
[8, 4, 7, 2, 3]


[2, 3, 4, 7, 8]

import random # random 메소드 사용을 위해 import

a = random.sample(range(1, 10), 5) # 1<= x < 10의 난수 5개 리스트로 생성
print(a) # 정렬 전 리스트
print('')
def quickSort(a, start, end):# 재귀함수용 함수 선언(리스트, 시작인덱스, 종료인덱스)
    # print(a)
    if start < end: # 시작 인덱스 보다 끝 인덱스가 클 경우
        left = start # left 변수에 시작 인덱스 할당
        pivot = a[end] #  //pivot 값은 a리스트에 마지막 원소 값
        for i in range(start, end): # 시작인덱스부터 끝 원소까지 반복
            if a[i] < pivot: # 리스트 인덱스 값이 pivot 값보다 작을 경우라면
                a[i], a[left] = a[left], a[i] #  해당 인덱스와 left인덱스  swap
                left += 1 # 인덱스 하나 증가 시켜주기(자리를 옮겨가며 비교해야 하기 때문에)
        a[left] , a[end] = a[end], a[left] # left인덱스와 끝 인덱스 swap
        print(left)
        quickSort(a, start, left-1) # 재귀 호출 (리스트, 시작 인덱스, left-1)
        quickSort(a, left+1, end) # 재귀 호출 (리스트, left+1, 종료인덱스)
quickSort(a, 0, len(a)-1)
print('')
print(a) # 정렬 후 리스트

#출력
[8, 1, 7, 2, 5]


[1, 2, 5, 7, 8]

import random # random 메소드 사용을 위해 import

a = random.sample(range(1, 10), 5) # 1<= x < 10의 난수 5개 리스트로 생성
print(a) # 정렬 전 리스트
print('')
def mergeSort(a):
    if len(a) > 1: # 배열의 길이가 1보다 클 경우 재귀함수 호출 반복
        mid = len(a)//2 # 2로 나눈 몫 (중간 값) 취함
        la, ra = a[:mid], a[mid:] # la 중간 값을 기준으로 왼쪽, ra 중간 값을 기준으로 오른쪽
        mergeSort(la) # 왼쪽 서브 리스트의 값을 기준으로 병합정렬 재귀 호출
        mergeSort(ra) # 오른쪽 서브 리스트의 값을 기준으로 병합정렬 재귀 호출
        li, ri, i = 0, 0, 0 # 정렬을 위한 변수 선언 (왼쪽, 오른쪽, 기준)
        while li < len(la) and ri < len(ra): # 서브 리스트의 정렬이 끝날 때까지 반복
            if la[li] < ra[ri]: # 오른쪽 리스트의 값이 클 경우라면
                a[i] = la[li] # 왼쪽 리스트의 해당 인덱스의 값을 할당
                li += 1 # 왼쪽 리스트의 인덱스 하나 증가
            else: # 왼쪽 리스트의 값이 클 경우라면
                a[i] = ra[ri] # 오른쪽 리스트의 해당 인덱스의 값을 할당
                ri += 1 # 오른쪽 리스트의 인덱스 하나 증가
            i += 1 # 기준 인덱스 증가
        a[i:] = la[li:] if li != len(la) else ra[ri:]
      # 왼쪽 리스트의 인덱스의 값이 서브 리스트의 값과 같지 않을 경우라면(정렬 끝),
      # 왼쪽 서브 리스트의 값을 리스트에 덮어쓰기, 그렇지 않은 경우라면 오른쪽 서브 리스트의 값 할당                                   
mergeSort(a)
print('')
print(a) # 정렬 후 리스트

#출력
[3, 2, 5, 9, 6]


[2, 3, 5, 6, 9]

import random # random 메소드 사용을 위해 import

a = random.sample(range(1, 10), 5) # 1<= x < 10의 난수 5개 리스트로 생성
print(a) # 정렬 전 리스트
print('')
def InsertionSort(x, start, gap): # 삽입정렬 구현
    for target in range(start+gap, len(x), gap): # (시작인덱스+차이, 리스트 크기만큼 반복, 차이까지)
        val = x[target] # 리스트의 값
        i = target #  인덱스 저장
        while i > start: #  증감 값 보다 인덱스가 크다면 반복
            if x[i-gap] > val: # 리스트의 비교 인덱스 값 보다 크다면
                x[i] = x[i-gap] #  해당 인덱스 값 할당
            else: # 리스트의 비교 인덱스 값 보다 작다면
                break # 반복 중지
            i -= gap #  중간 값만큼 빼주기
        x[i] = val # 해당 값 삽입

def shellSort(x): #
    gap = len(x) // 2 # 리스트를 2로 나눈 몫 (중간 값) 취함
    while gap > 0: #
        for start in range(gap): # 중간 값의 크기만큼 반복
            InsertionSort(x, start, gap) # 삽입정렬 메소드 호출 (리스트, 증감 값, 중간 값)
        gap = gap // 2 # 리스트를 2로 나눈 몫 (중간 값) 취함 (반으로 줄여나간다.)
shellSort(a)
print('')
print(a) # 정렬 후 리스트

#출력
[8, 4, 2, 3, 7]


[2, 3, 4, 7, 8]

import random # random 메소드 사용을 위해 import

a = random.sample(range(1,10,5) # 1<= x < 10의 난수 5개 리스트로 생성
print(a) # 정렬 전 리스트
print('')
def radixSort(a):
    isSort = False # 정렬 완료시 True
    index = 1 # 시작 인덱스
    while not isSort: # 정렬이 되지 않았다면 반복
        isSort = True # 정렬 상태 확인 변수
        sortList = [list()for _ in range(10)] # 빈 리스트 선언

        for num in a: # 리스트의 크기만큼 반복
            number = (int)(num/index)%10 # 자리 수를 기준으로 정렬하기 위한 변수 할당
            sortList[number].append(num) # 자리 수를 기준으로 리스트에 인덱스 선언
            if isSort and number > 0: # 정렬 되지 않았다면 && 자리 수 변수가 0보다 크다면
                isSort = False # 정렬 안 됨~

        i = 0 # 인덱스 증가용 변수 선언
        for number1 in sortList: # 정렬 리스트 크기만큼 반복
            for num in number1: # 증감 값의 크기만큼 반복
                a[i] = num # 리스트에 인덱스 값 넣기
                i += 1 # 인덱스 증가
        index *= 10 # 자리 수 증가
radixSort(a)
print('')
print(a) # 정렬 후 리스트

#출력
[8, 1, 4, 2, 5]


[1, 2, 4, 5, 8]

import random # random 메소드 사용을 위해 import
a = random.sample(range(1, 10), 5) # 1<= x < 10의 난수 5개 리스트로 생성
print(a) # 정렬 전 리스트 출력
a.sort() # 오름차순 정렬
print(a) # 정렬 후 리스트 출력
a.sort(reverse=True) # 내림차순 정렬
print(a) # 정렬 후 출력
print(sorted(a)) # sorted 함수 사용 정렬
print(sorted("This is a Moon's world".split(), key=str.lower)) # sorted 함수를 이용한 키 값 기준 정렬
b= [('abc','A',3), ('bcd','B',1), ('cde','C',15)] # 불특정 tuple을 갖는 리스트 생성
print(sorted(b, key=lambda b: b[2])) # tuple의 2번 째 요소를 가지고 정렬

# 출력
[4, 5, 8, 2, 6]
[2, 4, 5, 6, 8]
[8, 6, 5, 4, 2]
[2, 4, 5, 6, 8]
['a', 'is', "Moon's", 'This', 'world']
[('bcd', 'B', 1), ('abc', 'A', 3), ('cde', 'C', 15)]