Let’s solve Day 20: Sorting. Sorting algorithms are fundamental in computer science and play a crucial role in organizing and manipulating data efficiently. Join us on this exciting journey to explore the Bubble Sort algorithm and its implementation.😍
Task
Given an array a of size n distinct elements, sort the array in ascending order using the Bubble Sort algorithm. Once sorted, print the following three lines:
- Array is sorted in numSwaps swaps. where numSwaps is the number of swaps that took place.
- First Element: firstElement where firstElement is the first element in the sorted array.
- Last Element: lastElement where lastElement is the last element in the sorted array.
Sample Input
3
1 2 3Sample Output
Array is sorted in 0 swaps.
First Element: 1
Last Element: 3Explanation
To solve this challenge, we need to implement the Bubble Sort algorithm and keep track of the number of swaps that occur during the sorting process. The Bubble Sort algorithm works by repeatedly swapping adjacent elements if they are in the wrong order, until the entire array is sorted.
After sorting the array, we need to print three lines: the number of swaps that occurred, the first element of the sorted array, and the last element of the sorted array.
Day 20: Sorting Solution In Javascript
function swap(array, index1, index2) {
var temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
function main() {
const n = parseInt(readLine().trim(), 10);
const a = readLine().replace(/\s+$/g, '').split(' ').map(aTemp => parseInt(aTemp, 10));
let swapCount = 0;
for(let i = 0; i<n; i++){
for(let j = 0; j<n-1; j++){
if(a[j] > a[j+1] ){
swap(a,j,j+1);
swapCount++;
}
}
if(swapCount == 0){
break;
}
}
console.log(`Array is sorted in ${swapCount} swaps.`);
console.log(`First Element: ${a[0]}`);
console.log(`Last Element: ${a[n-1]}`);
}Day 20: Sorting Solution In C++
string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);
void swap(vector<int> &array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
int main() {
string n_temp;
getline(cin, n_temp);
int n = stoi(ltrim(rtrim(n_temp)));
string a_temp_temp;
getline(cin, a_temp_temp);
vector<string> a_temp = split(rtrim(a_temp_temp));
vector<int> a(n);
for (int i = 0; i < n; i++) {
int a_item = stoi(a_temp[i]);
a[i] = a_item;
}
int swapCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1; j++) {
if (a[j] > a[j + 1]) {
swap(a, j, j + 1);
swapCount++;
}
}
if (swapCount == 0) {
break;
}
}
cout << "Array is sorted in " << swapCount << " swaps." << endl;
cout << "First Element: " << a[0] << endl;
cout << "Last Element: " << a[n - 1] << endl;
return 0;
}Day 20: Sorting Solution In Java
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bufferedReader.readLine().trim());
List<Integer> a = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(Collectors.toList());
int swapCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1; j++) {
if (a.get(j) > a.get(j + 1)) {
Collections.swap(a, j, j + 1);
swapCount++;
}
}
if (swapCount == 0) {
break;
}
}
System.out.println("Array is sorted in " + swapCount + " swaps.");
System.out.println("First Element: " + a.get(0));
System.out.println("Last Element: " + a.get(n - 1));
bufferedReader.close();
}
}Day 20: Sorting Solution In Python
import math
import os
import random
import re
import sys
if __name__ == '__main__':
n = int(input().strip())
a = list(map(int, input().rstrip().split()))
swap_count = 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]
swap_count += 1
if swap_count == 0:
break
print("Array is sorted in {} swaps.".format(swap_count))
print("First Element:", a[0])
print("Last Element:", a[-1])Day 20: Sorting Solution In PHP
<?php
$n = intval(trim(fgets(STDIN)));
$a_temp = rtrim(fgets(STDIN));
$a = array_map('intval', preg_split('/ /', $a_temp, -1, PREG_SPLIT_NO_EMPTY));
$swapCount = 0;
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $n - 1; $j++) {
if ($a[$j] > $a[$j + 1]) {
$temp = $a[$j];
$a[$j] = $a[$j + 1];
$a[$j + 1] = $temp;
$swapCount++;
}
}
if ($swapCount == 0) {
break;
}
}
echo "Array is sorted in $swapCount swaps.\n";
echo "First Element: {$a[0]}\n";
echo "Last Element: {$a[$n - 1]}\n";Learning from this Question
By solving the “Day 20: Sorting” challenge, you can learn several important concepts:
- Bubble Sort algorithm: You will gain a practical understanding of the Bubble Sort algorithm and its implementation.
- Sorting algorithms: You will reinforce your knowledge of sorting algorithms, which are fundamental in computer science.
- Array manipulation: You will practice manipulating arrays and accessing their elements.
- Time complexity: You will learn about the time complexity of the Bubble Sort algorithm and its efficiency compared to other sorting algorithms.
- Problem-solving skills: You will enhance your problem-solving skills by designing and implementing a solution that meets the given requirements.
Conclusion
The “Day 20: Sorting” challenge introduces the Bubble Sort algorithm and its practical application in sorting an array. By implementing this algorithm and adhering to the given requirements, you will gain valuable experience in understanding sorting techniques and their importance in data manipulation and organization. The complete code for this challenge is available in my GitHub repository✨.
This exercise reinforces the significance of sorting algorithms in computer science and software development, as they form the backbone of many data processing tasks and ensure efficient data management⭐.
“If, at first, you do not succeed, call it version 1.0.”
― Khayri R.R. Woulfe