[Python] 이것이 코딩테스트다 6장 정렬

정렬의 핵심

 

	선택	삽입	퀵	계수	합병	버블
평균시간복잡도	O(n^2)	O(n^2)	O(nlogn)	O(N+K)	O(nlogn)	O(n^2)

 

• 선택 정렬  

선택 정렬은 코드가 구현하기 쉬우나, 데이터의 갯수가 늘어나면 늘어날 수록 현저히 느리게 작동하는 것을 확인 할 수있다 데이터가 많아지면 비효율적이다

 

 

• 삽입 정렬  

삽입 정렬은 선택 정렬과 같이 O(n^2)이지만 실제 실행시간 측면에서는 조금 더 효율적이라고 알려져 있다

그리고 거의 모든 데이터가 정렬이 되어있다면 삽입 정렬은 가장 효율성이 극대화된다

 

최선의 경우 O(N)의 시간까지 극대화 될 수 있다

즉, 거의 정렬이 되어있다면     속도 : 삽입정렬 > 퀵정렬 

 

 

• 퀵 정렬 

대부분 라이브러리 하면 사용되는 정렬.

기본적으로 분할을 이용하기 때문에 기하급수적으로 줄어들어 O(nlogn)과 같은 성능을 가질수 있음

 

하지만, 최악의 경우 O(n^2)의 성능이 나올수도 있다는 것이 단점!

우리가 쓰는 라이브러리에 구현된 퀵정렬은 최악의 상황에서도 O(nlogn)을 보장할 수 있도록 약간의 로직 처리가 되어있다

 

 

• 계수 정렬 

시간복잡도로만 보면 기수정렬과 더불어 가장 빠른 정렬법. 단점은 메모리가 사용이 많이된다

공간복잡도의 한계가 있기때문에 일반적으로 가장 큰 데이터와 가장 같은 데이터의 차이가 1000000을 넘지 않을때 효과적

동일한 값을 가지는 데이터가 많을 경우 유리하고 데이터 크기에 한정적이기 때문에 한정적으로 사용되어야 한다 

따라서 조건을 보고 유동적으로 사용

 

 

• 합병 정렬 

분할 정복에 대표적인 정렬 방법

데이터 분포에 상관없이 안정적인 O(nlog)의 성능을 보여주지만 추가적인 리스트를 사용해야함.

 

 

• 버블 정렬 

기초중에 기초 정렬 

앞뒤를 바꾸는 아이디어가 꼭 필요할 때가 있으므로 알아두는 것이 좋다

 

 

---

선택정렬 예제

 

 

📝 체감난이도 : ★☆☆☆☆

 

🎨 내가 짠 코드

 

 

 

 

🔑 Key Point 

 

최소를  선택할 수 있는 것만 알면 쉬움

 

---

삽입정렬 예제

 

 

📝 체감난이도 : ★☆☆☆☆

 

🎨 내가 짠 코드

 

 

 

 

 

 

🔑 Key Point 

 

삽입을 인덱스로 지정해서 하는것이 아니라 한 칸씩 목적지 까지 SWAP 해주어야 한다 

 

 

---

퀵 정렬 예제

 

 

📝 체감난이도 : ★★★☆☆

 

🎨 내가 짠 코드

 

 

 

 

 

 

 

 

🎨 파이썬 장점을 활용한 퀵정렬 구현

 

 

 

 

사실 이건 거의 분할정복 같단 생각이 들었는데 다시보니 Pivot을 이용했기 때문에 퀵정렬이라 하나보다

저자도 파이썬을 이용한 퀵정렬은 전통적인 퀵정렬의 분할 방식과는 다르다고 하였다.

암튼 이게 이해하기는 훨~씬 시우나 시간면에서는 전통적인 방법이 더 빠르다구 한다

 

 

 

 

 

 

🔑 Key Point 

 

 

 

퀵 정렬 구현은 사소한 조건들을 캐치해야해서, 구현하는데 좀 어려웠다😂

왼쪽 오른쪽 상한, 하한도 정해주어야 한다는 점과,

엇갈렸을 때만 피봇을 교체하여야하고(같을때 안됨), 원소가 1개라도 종료해야 하는것만 캐치를 잘 해야될 것 같다

 

---

계수 정렬 예제

 

 

 

📝 체감난이도 : ★☆☆☆☆

 

 

 

🎨 내가 짠 코드

 

 

 

 

 

🔑 Key Point 

 

인덱스 넣는곳에 값을 넣어 저장하기

 

 

---

위에서 아래로

 

 

 

📝 체감난이도 : ★☆☆☆☆

 

 

🎨 내가 짠 코드

 

 

 

 

 

 

🔑 Key Point 

 

매우 기본 예제 ! 입력받는 수가 500개 이하이므로 어느 정렬을 써도 무방함

 

 

---

성적이 낮은 순서로 학생 출력하기

 

 

 

📝 체감난이도 : ★☆☆☆☆

 

 

🎨 내가 짠 코드

 

 

 

 

🔑 Key Point 

이번엔 입력의 수가 1000000개 까지 이므로 최악의 경우 O(nlogn)의 이상 성능 보장하는 아무 알고리즘을 이용하면 된다.

라이브버리를 이용하면 될 듯하다!

 

이 문제는 해쉬 또는 딕셔너리 형태로 입력받아 Key값으로 정렬하면된다.

파이썬에서 그러한 정렬을 위해 lambda 가 제공된다

 

>>> str_list = ['헬로','go','개구리','nice']

>>> print(sorted(str_list, key=lambda x : x[1]))  # 람다
['nice', 'go', '개구리', '헬로']

>>> tuple_list = [('좋은하루', 0),
    	          ('niceday', 1), 
    	          ('좋은하루', 5), 
    	          ('good_morning', 3), 
    	          ('niceday',5)]
                  
>>> tuple_list.sort(key=lambda x : (x[0], x[1]))  # '-'부호를 이용해서 역순으로 가능
>>> print(tuple_list)
[('good_morning', 3), ('niceday', 1), ('niceday', 5), ('좋은하루', 0), ('좋은하루', 5)]

---

두 배열의 원소 교체

 

 

📝 체감난이도 : ★☆☆☆☆

 

 

🎨 내가 짠 코드

 

 

 

 

🎨 좀 더 효율적인 코드

 

 

 

 

🔑 Key Point 

 else를 생성하여 더이상 검사할 필요 없게 break를 걸어주면 좀 더 효율적이다

 

 

 

---

마무리

Sort는 너무 재미가 없었다

라이브러리가 있는데 굳이 왜 필요하나 하겠지만

분명 직접 구현해야 할 아이디어랑 부분이 있을 거다🎄