it doesn’t have an impact of time complexity
Nice to see a C# example.
“After all the elements have been compared, we swap the element with the smallest index with the first element index of the unsorted pile”
I suggest the edit above
“The time complexity of this algorithm, like before, is O(n^2), because it is essentially two nested loops.”
I suggest adding the word “nested” as indicated above
I think selection sort is stable, since we are only swapping the index if its smaller only then the relative order is unchanged.
I think this needs to be edited.
“”"
The idea for insertion sort is that you want to keep the smallest card in index zero and the rest of the
numbers you would want to shift it leftwards.
The stop condition is by the time you get to the last number, the array should be sorted.
Time complexity: O(n^2) as it is like ap operation
1 + 2 + … n - 1 →
“”"
def insertion_sort(arr: List[int]) → List[int]:
length = len(arr)
for i in range(1,length):
curr_val = arr[i]
for j in range(i, 0, -1):
comp_val = arr[j]
if curr_val < comp_val:
arr[i], arr[j] = arr[j], arr[i]
return arr
"""
The idea for insertion sort is that you want to keep the smallest card in index zero and the rest of the
numbers you would want to shift it leftwards.
The stop condition is by the time you get to the last number, the array should be sorted.
Time complexity: O(n^2) as it is like ap operation
1 + 2 + .... n - 1 ->
"""
def insertion_sort(arr: List[int]) -> List[int]:
length = len(arr)
for i in range(1,length):
curr_val = arr[i]
for j in range(i, 0, -1):
comp_val = arr[j]
if curr_val < comp_val:
arr[i], arr[j] = arr[j], arr[i]
return arr
The idea is to compare two elements and swap them if they are in wrong order.
Optimise by
- Checking if there are any more swaps to be made. If not, stop.
- Every time a swap is made, change the index of the array to the latest index of sorted array.
def v4_bubble_sort(arr):
n = len(arr)
list_sorted = False
while not list_sorted:
list_sorted = True
new_n = 0
for i in range(1, n):
first_number = arr[i-1]
second_number = arr[i]
if first_number > second_number:
arr[i], arr[i-1] = swap(arr[i-1], arr[i])
list_sorted = False
new_n = i # updating latest sorted index
n = new_n # stop sorting as the next n elements are already sorted
return arr
Nope, let’s think about an array: [4’, 3, 2, 4, 1]
After the first iteration, it becomes [1, 3, 2, 4, 4’] which is not stable.
using System;
class SortingAlgorithms
{
// Selection Sort
public static void SelectionSort(int arr)
{
int n = arr.Length;
// One by one move the boundary of unsorted subarray
for (int i = 0; i < n - 1; i++)
{
// Find the minimum element in unsorted array
int minIndex = i;
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
// Bubble Sort
public static void BubbleSort(int[] arr)
{
int n = arr.Length;
// Traverse through all array elements
for (int i = 0; i < n - 1; i++)
{
// Last i elements are already in place
for (int j = 0; j < n - i - 1; j++)
{
// Traverse the array from 0 to n-i-1
// Swap if the element found is greater than the next element
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Insertion Sort
public static void InsertionSort(int[] arr)
{
int n = arr.Length;
for (int i = 1; i < n; i++)
{
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// Merge Sort
public static void MergeSort(int[] arr)
{
if (arr.Length <= 1)
return;
int mid = arr.Length / 2;
int[] left = new int[mid];
int[] right = new int[arr.Length - mid];
Array.Copy(arr, 0, left, 0, mid);
Array.Copy(arr, mid, right, 0, arr.Length - mid);
MergeSort(left);
MergeSort(right);
Merge(arr, left, right);
}
private static void Merge(int[] arr, int[] left, int[] right)
{
int i = 0, j = 0, k = 0;
while (i < left.Length && j < right.Length)
{
if (left[i] <= right[j])
{
arr[k] = left[i];
i++;
}
else
{
arr[k] = right[j];
j++;
}
k++;
}
while (i < left.Length)
{
arr[k] = left[i];
i++;
k++;
}
while (j < right.Length)
{
arr[k] = right[j];
j++;
k++;
}
}
// Quick Sort
public static void QuickSort(int[] arr, int low, int high)
{
if (low < high)
{
int pivotIndex = Partition(arr, low, high);
QuickSort(arr, low, pivotIndex - 1);
QuickSort(arr, pivotIndex + 1, high);
}
}
private static int Partition(int[] arr, int low, int high)
{
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++)
{
if (arr[j] < pivot)
{
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp2 = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp2;
return i + 1;
}
// Heap Sort
public static void HeapSort(int[] arr)
{
int n = arr.Length;
for (int i = n / 2 - 1; i >= 0; i--)
Heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--)
{
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
Heapify(arr, i, 0);
}
}
private static void Heapify(int[] arr, int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
Heapify(arr, n, largest);
}
}
// Print the array
public static void PrintArray(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
Console.Write(arr[i] + " ");
}
Console.WriteLine();
}
// Main method for testing the sorting algorithms
static void Main()
{
int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
Console.WriteLine("Original array:");
PrintArray(arr);
Console.WriteLine("\nSelection Sort:");
SelectionSort(arr);
PrintArray(arr);
Console.WriteLine("\nBubble Sort:");
BubbleSort(arr);
PrintArray(arr);
Console.WriteLine("\nInsertion Sort:");
InsertionSort(arr);
PrintArray(arr);
Console.WriteLine("\nMerge Sort:");
MergeSort(arr);
PrintArray(arr);
Console.WriteLine("\nQuick Sort:");
QuickSort(arr, 0, arr.Length - 1);
PrintArray(arr);
Console.WriteLine("\nHeap Sort:");
HeapSort(arr);
PrintArray(arr);
}
}
I think that all SplitWords() in C# solutions across multiple sections can be deleted, simplified and replaced with Console.ReadLine().Split().Select(int.Parse).ToList();
In the sorting algorithm C++ code template what is the purpose of:
ss >> std::boolalpha;
And when does it become true and false when the input is only numbers here eg: 5 3 7 8 2
Insertion sort - Python:
for i, entry in enumerate(unsorted_list):sinceentryis not used, this could just becomefor i in range(0, len(unsorted_list)):Overall, the time complexity is O(n * (n + 1) / 2): can this be clarified? how come the inner loop has this time complexity?(n + 1) / 2
In Selection Sort there is no need to swap if the min index equals the current i index:
public static List<Integer> sortList(List<Integer> unsortedList) {
int n = unsortedList.size();
for (int i = 0; i < n; i++) {
// Assume the current position as minimum
int minIndex = i;
// Find the minimum element's index from the rest of the list
for (int j = i; j < n; j++) {
if (unsortedList.get(j) < unsortedList.get(minIndex)) {
minIndex = j;
}
}
//SWAP if minIndex <> i
if (minIndex != i) {
int temp = unsortedList.get(i);
// Swap the minimum element with the first element
unsortedList.set(i, unsortedList.get(minIndex));
unsortedList.set(minIndex, temp);
}
}
return unsortedList;
}
And it looks like this condition makes the algorithm stable.
The selection sort algorithm could be made stable by reversing the range of the nested for loop!
This is just me perhaps but it’s really confusing that you say to try and do a sort algorithm before explaining the different options. Is that intentional?