정렬(Sort) 알고리즘_버블 정렬, 카운팅 정렬

알고리즘 문제를 풀때 기본이 되는 개념은 정렬(Sort)입니다.
대부분 input값을 입력받고 output을 내야하는 문제상황속에서 내가 원하는 결과를 내기 위해서는
입력받은 자료를 문제를 풀기위한 구조로 재배열하는 작업이 필수적이기 때문입니다.
정렬에는 여러종류가 있지만 그 중에서 기초적인 개념 '버블 정렬', '카운팅 정렬'에 대한 내용입니다.

 

---

📌 정렬의 종류

• 버블 정렬(Bubble Sort)
• 카운팅 정렬(Counting Sort)
• 선택 정렬(Selection Srot)
• 퀵 정렬(Quick Sort)
• 삽입 정렬(Insertion Sort)
• 병합 정렬(Merge Srot)

 

시간복잡도 빅오 O()

시간복잡도를 확인하고 상황에 맞는 정렬을 사용하자!

많은 양의 데이터들을 다루다보면 그 데이터들을 연산하는 속도에 민감해져야합니다.
알고리즘 문제에 시간제한이 있는 경우도 있지만 근본적으로 더 효율적인 프로그래밍을 위함이기도 하죠.
따라서 정렬별 시간복잡도를 알아야하고, 상황에 맞춰서 적절한 정렬을 사용할 줄 알아야합니다.

 

빅오 - 시간복잡도 그래프

 

🛁 버블 정렬(Bubble Sort)

거품모양 처럼 한자리씩 이동하는 버블 정렬(Bubble Sort)

버블 정렬은 간단한 정렬 중에 하나로, 인접한 두개의 원소를 비교하며 자리를 계속 교환하는 방식입니다.

다음과 같은 리스트가 있을 때, 리스트를 오름차순으로 정렬하려고 한다고 가정해보겠습니다.
작은 수 부터 큰 수로 정렬을 해야하기 때문에 맨 앞에 25는 맨 뒤로 가야합니다.

버블 정렬은 리스트의 첫번째 원소를 다음 원소들과 계속해서 비교해 값이 크다면 교환합니다.
그렇다면 한번의 반복이 진행된다면 맨 앞의 '25'는 가장 큰 값이므로 맨 뒤에 위치하게 됩니다.

 

 List = [25, 3, 8, 11, 15, 9]

 

파이썬 내장함수인 Sort(), sorted()가 있지만 간단한 for문으로 함수를 구현해 볼 수 있습니다.

 

  def bubbleSort(x):
    length = len(x)-1
    for i in range(length):
        for j in range(length-i):
            if x[j] > x[j+1]:
                x[j], x[j+1] = x[j+1], x[j]
    return x

 

거품이 마치 수면위로 올라오는 듯한 원리를 가지고 있어 이름이 붙여진 '버블 정렬'은

시간복잡도가 느린 방법 중에 하나입니다.

 

• 버블정렬 시간복잡도 : O(n^2)

하지만 코드가 단순하여 자주 쓰이는 정렬 중에 하나이고, 양방향으로 번갈아 수행하면
칵테일 정렬로 구현해 볼 수 도 있습니다.

 

🧮 카운팅 정렬

개수를 세는 리스트를 만들어주자!

카운팅 정렬은 쉽게 말하면,
리스트에 있는 원소 개수를 세기 위해 개수를 기록하는 또 다른 리스트를 만들어 주는 방식입니다.
다음과 같은 리스트가 있을 때 가장 많거나 적게 등장하는 숫자를 찾을 때나,
가장 적게 등장하는 숫자부터 오름차순으로 정렬하기 위해 사용할 수 있습니다.

 

    cnt = [] # 인덱스를 기준으로 아래 숫자를 카운팅해주는 리스트 생성

    List = [1, 1, 1, 2, 3, 5, 5, 6, 7, 7, 8, 8, 8, 9, 9, 9, 9]

카운팅 정렬은 정수나 정수로 표현할 수 있는 자료에 대해서만 적용이 가능합니다.
카운팅을 하기위한 적절한 리스트를 만들어 내는 것이 중요하며,
리스트 내 정수의 최댓값이 작다면 매우 효율적인 퍼포먼스를 보여주는 정렬입니다.

 

• 카운팅 정렬 시간복잡도 : O(n + k)
• n은 리스트 길이, k는 정수의 최대값.

 

마치며..

정렬은 입력받은 데이터 구조가 복잡해질 수록 상황에 맞는 정렬을 잘 적용해야합니다.
먼저 기초적인 정렬에 대한 이해를 바탕으로 계속해서 심화된 정렬들을 익히고 많은 문제를
풀어보며 상황에 맞는 정렬을 적용할 수 있도록 익숙해져야 합니다.

 

이후에 여러 문제들에 대한 리뷰와 함께 더 많은 정렬에 대한 내용을 포스팅 하겠습니다.

감사합니다 :)

 

 

 

* 참고문서

• 위키 백과 : ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC