Day 20 - Sorting

문제풀이>HackerRank

마침 요새 JavaScript에서도 sort() 메서드를 배우고 있는데, 그 안의 복잡한 알고리즘을 보면서, 대충 척 보면 바로 sorting해내는 인간의 뇌가 참 대단하다고 느꼈다.이를 코드로 구현해보는 이 문제를 푸는 데엔 뇌가 썩 신속히 협조해주지 않았지만.

문제 풀이

문제 해석

Bubble sort라는 것을 코드로 구현하라는 것인데 이것은 원본 리스트의 숫자들이 오름차순으로 정렬되면서, 정렬을 위해 몇 번 바꿔치기가 일어나는지도 기록해야 하는 까다로운 문제이다. 바꿔치기는 인덱스 순서대로 순회하며 앞쪽 요소가 뒤쪽 요소보다 클 경우 뒤로 보내는 것이 1번의 횟수로 기록된다.

Task

  • n개의 각기 다른 요소를 가진 a라는 배열이 주어질텐데, 오름차순으로 정렬
  • 다음 세 개를 출력하게끔 하라.
    • numSwaps: 바꿔치기의 횟수
    • firstElement: 정렬 후 첫 요소
    • lastElement: 정렬 후 마지막 요소
  • 힌트: 새로운 변수를 만들어 거기에 바꿔치기 횟수를 기록해야 한다는 것

Input Format

  • 첫 줄은 a 리스트의 요소 갯수인 n
  • 두 번째 줄은 공백으로 구분된 n개의 정수들

Output Format

  • 아래 세 줄이 상응하는 값과 함께 출력되어야 한다.
  • Array is sorted in numSwaps swaps.
  • First Element: firstElement
  • Last Element: lastElement

문제 풀이

이미 주어진 코드 해석

1
2
3
4
import sys

n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
  • sys를 import한 것의 뜻은 언젠가 알게 되겠지…
  • n개의 요소를 받아서 공백을 기준으로 잘라 리스트 안에 하나하나씩 정수로 담아주는 작업이 되어있음을 알 수 있다.

코드 작성하기

  • 리스트를 순회하면서 n번째 요소와 n+1번째 요소에 바꿔치기 작업 (인덱스값을 서로 바꾼 값을 할당한다)
  • 만약 바꿔치기가 진행된 경우 해당 횟수를 카운트해야 하므로 카운트 할 변수 numSwap에 0이라는 초기값을 할당하며, n+1번쨰 요소가 더 작을 경우, 즉 바꿔치기 작업이 일어날 경우에만 증가시킨다.
  • 한번 쭉 돌면 앞에서부터의 두 요소씩 비교한 후의 작업이 끝난 것일 뿐 서로 떨어져 있는 두 요소가 비교되지 못했으므로 처음부터 다시 가서 n번 돌아야 모든 요소가 오름차순 정렬에 맞는 바꿔치기 작업이 수행된다. (이부분은 이해하기 난해한데 그냥 for문을 써보면서 하면 더 쉽다.)
  • 그러므로 for문 안의 for문으로 두 번의 반복을 돌린다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    for i in range(n):
        num_swap = 0    
        for j in range(n-1):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                num_swap += 1
        if num_swap == 0:
            break

    print('Array is sorted in {} swaps.'.format(num_swap))
    print('First Element: {}'.format(a[0]))
    print('Last Element: {}'.format(a[n-1]))

느낀 점

  • 참고하라고 주어진 JavaScript의 Bubblesort에는 마지막에 numSwap이 0인 경우 break문이 있는데, n으로 이미 for문이 끝날텐데 왜 있는 건지 궁금하다.
  • 요새 JS에서 sort를 배워서 타이밍 좋게 sort의 알고리즘을 생각해본 문제였다.

2021.05.14 자문자답 update

  • Bubble Sort 공부를 했다
  • 느낀점에서 왜 break가 있는지 궁금해했던 2달 전의 나에게 대답해주기
    • inner for문을 돌린 후 num_swap이 0인 경우는 곧 모든 요소가 오름차순으로 정렬되어 있으니 그 이후에는 swap을 할 필요가 없음을 의미한다.
    • 굳이 다시 하나하나 앞 요소와 그다음 요소를 비교하는 작업을 n번 더 돌릴 필요가 없으니 바로 break해주면, 원래는 O(n2)의 시간복잡도를 갖는 for문이 (처음부터 오름차순으로 정렬되어있는 배열에 대해서는) O(n)으로까지 줄어든다.
  • 그리고 inner for문에서는 range를 n-1까지 할 필요 없이 이미 정렬된 뒤쪽 요소들은 index만큼 덜 돌아도 된다!
    1
    2
    3
    4
    5
    6
    7
    8
    for i in range(n):
        num_swap = 0    
        for j in range(n-1-index):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                num_swap += 1
        if num_swap == 0:
            break
Python

Related posts

Day 7 - Arrays
Day 12 - 2D Arrays
Day 14 - Scope