[코딩테스트]정렬

📖정렬

데이터를 특정한 기준에 따라서 순서대로 나열하는 것.

📌가장 많이 사용하는 정렬 알고리즘

//(데이터가 무작위로 여러 개 있는 경우)

1. 선택 정렬: 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복. (가장 작은 것을 선택)
   → 시간복잡도: O(N^2)
2. 삽입 정렬: 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입. 거의정렬되어있는 경우에는 매우 효율적.
   → 시간복잡도: O(N^2)
3. 퀵 정렬: 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈. 거의정렬되어있는 경우에는 매우 비효율적.
   → 시간복잡도: O(NlogN)
4. 계수 정렬: 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘. 정수형태로 표현할 수 있을 때만 사용 가능.
   → 시간복잡도: O(N+K)

📌파이썬 정렬 라이브러리

sorted()
▪ 병합정렬 기반.
▪ 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과 출력.
▪ 집합 자료형이나 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
result = sorted(array)
print(result)

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

sort()
▪ 리스트 변수가 하나 있을 때 내부 원소를 바로 정렬할 수 있음.
▪ 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬됨.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
array.sort()
print(array)

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

▪ key 매개변수를 입력받아 사용하는 경우

array = [('바나나', 2), ('사과', 5), ('당근', 3)]
def setting(data)
    return data[1]   
result = sorted(array, key=setting)
print(result)

[('바나나', 2), ('당근', 3), ('사과', 5)]

📒이것이 취업을 위한 코딩테스트다 with 파이썬 책을 참고하여 작성하였습니다.
https://www.hanbit.co.kr/store/books/look.php?p_code=B8945183661