Sorting: Bubble Sort

가장 기초적인 sorting 알고리즘인 bubble sorting 구현문제이다.

Problem

Given an array of integers, sort the array in ascending order using the Bubble Sort algorithm above. Once sorted, print the following three lines:

1. Array is sorted in numSwaps swaps., numSwaps where is the number of swaps that took place.
2. First Element: firstElement, where firstElement is the first element in the sorted array.
3. Last Element: lastElement, where lastElement is the last element in the sorted array.

Sorting의 가장 기본적인 bubble sort의 구현문제이다. $O(n^2)$의 complexity를 갖는 알고리즘으로 실무적으로는 사용이 어렵다. 다만 실무에서는 어차피 built-in sorting을 사용하거나 NumPy같은 numerical computing package에서 최적화된 방법을 제공하므로 학습목적으로만 사용하는 알고리즘이다.

Answer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def countSwaps(a):
    # Write your code here
    length = len(a)
    swap_count = 0
    for i in range(length - 1):
        for j in range(length - 1):
            if a[j] > a[j+1]:
                a[j+1], a[j] = a[j], a[j+1]
                swap_count += 1
    print(f"Array is sorted in {swap_count} swaps.")
    print(f"First Element: {a[0]}")
    print(f"Last Element: {a[-1]}")

Explanation

계산비용이 큰 만큼 구현은 간단하다. Array를 처음부터 sweep하면서 가장 작은 수를 찾아 앞으로 가져오는 작업을 $n$번 반복한다. 이를 $n$개에 대해 해야하므로 $O(n^2)$이 된다.

Reference

• HackerRank