Day20 - Sorting (Python 3)

• URL : https://www.hackerrank.com/challenges/30-sorting/problem

• Objective
  • Today, we’re discussing a simple sorting algorithm called Bubble Sort. Check out the Tutorial tab for learning materials and an instructional video!
• Consider the following version of Bubble Sort:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

for (int i = 0; i < n; i++) {
    // Track number of elements swapped during a single array traversal
    int numberOfSwaps = 0;
    
    for (int j = 0; j < n - 1; j++) {
        // Swap adjacent elements if they are in decreasing order
        if (a[j] > a[j + 1]) {
            swap(a[j], a[j + 1]);
            numberOfSwaps++;
        }
    }
    
    // If no elements were swapped during a traversal, array is sorted
    if (numberOfSwaps == 0) {
        break;
    }
}

• Task
  • Given an array, a, of size n distinct elements, sort the array in ascending order using the Bubble Sort algorithm above. Once sorted, print the following 3 lines:
    • Array is sorted in numSwaps swaps.
      • where numswaps is the number of swaps that took place.
    • First Element: firstElement
      • where first element is the first element in the sorted array.
    • Last Element: lastElement
      • where last element is the last element in the sorted array.

• Hint: To complete this challenge, you will need to add a variable that keeps a running tally of all swaps that occur during execution.

• Input Format
  • The first line contains an integer, n, denoting the number of elements in array a.
  • The second line contains n space-separated integers describing the respective values of a0, a1 . . .an-1.
• Constraints
  • 2 <= n <= 600
  • 1 <= ai <= 2 * 10^6, where 0 <= i <= n.
• Output Format
  • Print the following three lines of output:
    • Array is sorted in numSwaps swaps.
      • where numSwaps is the number of swaps that took place.
    • First Element: firstElement
      • where first elementis the first element in the sorted array.
    • Last Element: lastElement
      • where last element is the last element in the sorted array.

문제 풀이

• n개의 원소를 가지는 a라는 리스트가 주어짐
• 리스트는 정렬이 안되어 있는데, 해당 리스트를 오름차순으로 정렬
• 정렬하는데 숫자를 바꾼 횟수를 저장하고, 가장 앞에있는 수와 가장 뒤에있는 수를 출력
• 가장 앞에 있는 수와 가장 뒤에 있는 수는 리스트의 min, max로 해결
• 정렬 횟수는 앞에 인덱스와 뒤의 인덱스를 비교하여 앞이 뒤보다 크면 앞뒤를 바꾸는 방식으로 for문을 만듬

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import sys

n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
# Write Your Code Here
numswaps = 0
for i in range(n):
    for j in range(n-1):
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]
            numswaps += 1
    if numswaps == 0:
        break

print(f'Array is sorted in {numswaps} swaps.')
print('First Element:', min(a))
print('Last Element:', max(a))

1
2
3
4
5
6
7

 3
 3 2 1


Array is sorted in3 swaps.
First Element: 1
Last Element: 3