08. 정렬 알고리즘 개념 및 풀이

 

 

01. 정렬 알고리즘이란?

 

정렬(sorting)이란,
순서없이 나열된 자료를 특정한 키값에 따라
오름차순이나 내림차순으로 자료를 재배열한 것을 의미한다.

 

정렬 알고리즘이 왜 필요할까?

탐색 효율을 높이기 위해서다. 도서관에서도, 원하는 책을 효율적으로 탐색하기 위해서 책이 순서대로 정렬되어있어야 한다. 도서관을 떠올리면 정렬의 필요성을 이해하기 쉽다.

 

 

---

 

02. 정렬 알고리즘의 종류

 

 

2-1. 선택정렬

 

가장 작은 노드(최소값)를 선택하고 왼쪽부터 정렬을 하기 위해 알맞은 위치와 교환하는 작업을 반복하는 것을 뜻한다.

O(n^2)번의 시간복잡도가 필요하며, 작은 수를 하나하나 순차적으로 찾아서 정렬해야 하므로 안정적이지 않다.

 

 

 

2-2. 삽입정렬

 

삽입정렬은 아직 정렬되지 않은 특정 노드와 정렬된 노드들의 값을 비교하고 값이 더 큰 것의 인덱스보다 작은 인덱스에 찾아 삽입하며 정렬하는 알고리즘이다.

 

최적의 경우 O(n)에서 최악의 경우 O(n^2)번까지 시행이 가능하다.

소량 데이터 처리에 유용하다. 왜냐하면 특정 노드값을 선택해, 타 노드들과 비교해 넣으면 되기 때문이다.

 

 

2-3. 버블정렬

 

이웃노드와 비교해서 더 크면 오른쪽으로 자리를 바꾸는 작업을 하는 알고리즘이다.

모든 노드를 비교해야 해서 O(n^2)번의 시간복잡도가 소요된다.

하지만 바로 옆 데이터와 비교하면 되므로 안정적이다. (👉🏻 선택정렬 대비 장점)

 

 

 

---

 

 

03. 정렬 알고리즘 풀이

 

3-1. 일부 list에서의 k번째 수 구하기

풀이시간: 5분

def solution(array, commands):
    answer = []
    for i in commands:
        answer_list = array[i[0]-1:i[1]]
        answer_list.sort()
        answer.append(answer_list[i[2]-1])
    return answer

 

 

 

3-1. list 내 숫자 조합으로 가장 큰 수 만들기

풀이시간: 35분

 

이 문제는, (1) int 리스트의 str화 & (2) 문자 sort & (3) join 작업이 필요하다.

이때 나는 (1)과 (3)는 올바르게 했지만, (2)를 해결하는 방법을 떠올리지 못했다. 즉, 문자열을 자릿수마다 순차적으로 비교하기 위한 for loop를 구상했다... 잘 해결되지 않아 구글링을 해보니, '문자열은 자체적으로 자릿수(ascii로 변환)마다 순차적으로 크기를 비교한다'는 것을 알게됐다. 중요한 부분을 배웠다!

 

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers)))

 

🔥 이 알고리즘의 핵심?

1. 문자 정렬의 경우, 알아서 0번째부터 n번째까지 순차적으로 비교해 ascii 숫자값에 의거하여 정렬한다.
2. 자릿수가 모두 동일하지 않으므로 x*3 값을 key로 하여 sort해준다. 

 

 

 

3-1. H-Index 구하기

풀이시간: 10분

def solution(citations):
    for i in range(len(citations),0, -1):
        cnt = 0
        for k in citations:
            if k>=i:
                cnt += 1
        if cnt == i :
            return i ​