ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

PowerShell: Implement Quick Sort with Lomuto Partition Scheme

PowerShell

Goal -- WPM

Ready
Exercise Algorithm Area
1function Partition-Lomuto {

2param(

3[int[]]$Array,

4[int]$Low,

5[int]$High

6)

7

8# Pivot (element to be placed at right position)

9$pivot = $Array[$High]

10

11# Index of smaller element

12$i = $Low - 1

13

14for ($j = $Low; $j -lt $High; $j++) {

15# If current element is smaller than the pivot

16if ($Array[$j] -lt $pivot) {

17$i++ # increment index of smaller element

18# Swap $Array[$i] and $Array[$j]

19$temp = $Array[$i]

20$Array[$i] = $Array[$j]

21$Array[$j] = $temp

22}

23}

24

25# Swap $Array[$i + 1] and $Array[$High] (or pivot)

26$temp = $Array[$i + 1]

27$Array[$i + 1] = $Array[$High]

28$Array[$High] = $temp

29

30return ($i + 1) # Return the partitioning index

31}

32

33function QuickSort-Recursive {

34param(

35[int[]]$Array,

36[int]$Low,

37[int]$High

38)

39

40# Base case: if the subarray has 0 or 1 elements, it's already sorted

41if ($Low -ge $High) {

42return

43}

44

45# Partition the array around a pivot

46$pivotIndex = Partition-Lomuto $Array $Low $High

47

48# Recursively sort elements before partition and after partition

49QuickSort-Recursive $Array $Low ($pivotIndex - 1)

50QuickSort-Recursive $Array ($pivotIndex + 1) $High

51}

52

53function QuickSort {

54param(

55[int[]]$ArrayToSort

56)

57

58$n = $ArrayToSort.Length

59

60# Handle empty or single-element array edge cases

61if ($n -le 1) {

62return $ArrayToSort

63}

64

65# Call the recursive helper function

66QuickSort-Recursive $ArrayToSort 0 ($n - 1)

67

68return $ArrayToSort

69}

70

71# Example Usage:

72# $myArray = @(10, 7, 8, 9, 1, 5)

73# $sortedArray = QuickSort $myArray

74# Write-Host "Sorted array: $($sortedArray -join ', ')"
Algorithm description viewbox

PowerShell: Implement Quick Sort with Lomuto Partition Scheme

Algorithm description:

This PowerShell script implements the Quick Sort algorithm using the Lomuto partition scheme. Quick Sort is a highly efficient, comparison-based sorting algorithm that uses a divide-and-conquer strategy. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This is a common choice for general-purpose sorting due to its average-case performance.

Algorithm explanation:

The `QuickSort` function serves as the entry point, handling initial checks and calling the recursive helper `QuickSort-Recursive`. The `Partition-Lomuto` function implements the Lomuto partition scheme. It selects the last element as the pivot, iterates through the array, and places all elements smaller than the pivot to its left. Finally, it places the pivot in its correct sorted position and returns its index. `QuickSort-Recursive` then recursively calls itself on the sub-arrays to the left and right of the pivot. The time complexity is O(n log n) on average and O(n^2) in the worst case (e.g., already sorted array with pivot as first/last element). Space complexity is O(log n) on average due to recursion stack depth, and O(n) in the worst case. Edge cases include empty arrays, single-element arrays, and handling the indices correctly during partitioning and recursion.

Pseudocode:

Function Partition-Lomuto(Array, Low, High):
  pivot = Array[High]
  i = Low - 1
  For j from Low to High - 1:
    If Array[j] < pivot:
      i = i + 1
      Swap Array[i] and Array[j]
  Swap Array[i + 1] and Array[High]
  Return i + 1

Function QuickSort-Recursive(Array, Low, High):
  If Low < High:
    pivotIndex = Partition-Lomuto(Array, Low, High)
    QuickSort-Recursive(Array, Low, pivotIndex - 1)
    QuickSort-Recursive(Array, pivotIndex + 1, High)

Function QuickSort(ArrayToSort):
  n = length of ArrayToSort
  If n <= 1:
    Return ArrayToSort
  QuickSort-Recursive(ArrayToSort, 0, n - 1)
  Return ArrayToSort