정렬

정렬의 종류

선택정렬	특정 리스트에서 가장 작은 데이터를 선택해서 앞으로 보내면서 정렬해주는 방법으로 시간이 오래걸림
삽입정렬	데이터를 확인하며 각 데이터를 적절한 위치에 삽입하는 정렬로 특정 숫자의 왼쪽 부분들은 이미 정렬된 것으로 가정함. 특정숫자의 왼쪽부터 처음에 위치한 배열의 숫자까지 for문을 돌리며 앞의 숫자가 더 작다면 그 뒤에 특정숫자를 삽입해줌.
퀵 정렬 = 피벗정렬	pivot을 기준으로 pivot보다 작은 숫자들을 왼쪽으로 큰 숫자들을 기준점 오른쪽으로 옮기며 이 과정을 반복하다보면 정렬됨
계수정렬	가장 큰 숫자와 가장 작은 숫자의 차이+1개 만큼의 배열을 선언하고 배열의 원소 번호와 같은 숫자일 경우 +1을 끝까지 해줘서 각 원소에 저장된 숫자만큼 원소번호를 출력하는 것을 끝까지 해주는 정렬
내장함수 활용	1. [정렬하고싶은 list명].sort(조건작성가능) 2. [정렬후 받을 list명] = [정렬하고싶은 list명].sorted(조건작성가능)

---

코드를 알아보며 정렬방법 이해하기

1. 선택정렬

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

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

print(array)

*알아둬야할 것 

=> c언어에서는 temp라는 빈 변수를 사용해서 swap을 했다면 python은 swap이 한줄로 가능

 

2. 삽입정렬

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. 퀵 정렬 = 피벗정렬

3- 1. left와 right로 부터 탐색하며 left와 right에서 찾은 pivot보다 작은 값과 큰 값의 위치가 크로스 된 경우 stop하고 pivot을 다시 설정하며 재귀적으로 정렬 => python의 장점을 사용하기 전

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

def quick_sort(array,start,end):
    if start>=end:
        return
    p = start
    left = start+1
    right = end
    while left<=right:
        while left<=end and array[left]<=array[p]:
            left+=1
        while right>start and array[right]>=array[p]:
            right-=1
        if left>right:
            array[right],array[p] = array[p],array[right]
        else:
            array[left], array[right] = array[right]=array[left]
        quick_sort(array,start,right-1)
        quick_sort(array,right+1, end)

quick_sort(array,0,len(array)-1)
print(array)

3 - 2. python의 장점을 살려 pivot보다 작은 값들과 큰 값들을 나누는데 짧게 작성가능

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

def quick_sort(array):
    if len(array)<=1:
        return array
    
    p = array[0]
    tail = array[1:]
    
    left_side = [x for x in tail if x<=p] # tail중에서 p보다 작은 것들을 left_side에 저장
    right_side = [x for x in tail if x>p] 

    return quick_sort(left_side)+[p]+quick_sort(right_side)


quick_sort(array,0,len(array)-1)
print(array)

4. 계수정렬

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

count = [0]*(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=' ')

5. 내장함수를 활용한 정렬

튜플을 활용한 예제에서는 setting을 활용 or lambda를 활용 => key의 활용방법

array=[('바나나',2),('사과',5)]

def setting(data):
    return data[1]

result = sorted(array, key=setting)
result2 = sorted(array,key=lambda x : x[1])

print(result, result2)

---

기본 예제

1. 위에서 아래로 = 오름차순으로 정렬하는 예제 => 입력받을 값의 개수 num이 적을때는 계수정렬을 활용할 수 있고 알아서 위에서 살펴본 개념을 가지고 작성해보자!

num = int(input()) # 1. 숫자를 입력받고 

list_=[]

for i in range(0,num):
    list_.append(int(input()))
# 2. 입력받은 숫자만큼 list_에 숫자를 입력받아 저장해줌

list_.sort(reverse=True)
# 3. 입력받은 숫자를 정렬할 때 reverse = True를 활용할 수 있음 [.sorted를 활용할 수도 있음]

for i in range(0,len(list_)):
    print(list_[i],end=' ')

2.  성적이 낮은 순서대로 출력

ex) 2

     김땡땡 89 

     이땡땡 40

를 입력했을 때 성적이 낮은 순서대로 이름을 출력하면 됨

num = int(input())
list_=[]

for i in range(0,num):
    list_.append(tuple(input().split()))

list_.sort(key = lambda x : x[1])

for i in range(0, num):
    print(list_[i][0],end=' ')

성적이 높은 순서대로 출력하려면? => reverse=True로 만들면 됨