Day20 - Sorting (Python 3)
Post
Cancel

# Day20 - Sorting (Python 3)

• 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; } } ```
• 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 ```