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

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

CQL: Implement Quick Sort

Cassandra CQL

Goal -- WPM

Ready
Exercise Algorithm Area
1CREATE OR REPLACE FUNCTION quick_sort(

2arr list<int>,

3low int,

4high int

5)

6RETURNS list<int>

7AS $$

8DECLARE

9pivot_index int;

10sorted_arr list<int>;

11BEGIN

12sorted_arr = arr; -- Work on a copy to avoid modifying original if needed elsewhere

13

14-- Base case: if the list has 0 or 1 element, it's already sorted

15IF low < high THEN

16-- Partition the array and get the pivot index

17pivot_index = partition(sorted_arr, low, high);

18

19-- Recursively sort elements before and after partition

20sorted_arr = quick_sort(sorted_arr, low, pivot_index - 1);

21sorted_arr = quick_sort(sorted_arr, pivot_index + 1, high);

22END IF;

23

24RETURN sorted_arr;

25END; $$

26

27CREATE OR REPLACE FUNCTION partition(

28arr list<int>,

29low int,

30high int

31)

32RETURNS int

33AS $$

34DECLARE

35pivot_value int;

36i int;

37j int;

38temp int;

39BEGIN

40-- Choose the pivot (last element in this implementation)

41pivot_value = arr[high];

42i = low - 1; -- Index of smaller element

43

44FOR j = low TO high - 1 DO

45-- If current element is smaller than or equal to pivot

46IF arr[j] <= pivot_value THEN

47i = i + 1;

48-- Swap arr[i] and arr[j]

49temp = arr[i];

50arr[i] = arr[j];

51arr[j] = temp;

52END IF;

53END FOR;

54

55-- Swap arr[i+1] and arr[high] (put pivot in its correct place)

56temp = arr[i + 1];

57arr[i + 1] = arr[high];

58arr[high] = temp;

59

60RETURN i + 1; -- Return the partitioning index

61END; $$

62

63-- Initial call wrapper for convenience

64CREATE OR REPLACE FUNCTION quick_sort_wrapper(

65arr list<int>

66)

67RETURNS list<int>

68AS $$

69DECLARE

70n int;

71BEGIN

72n = list_size(arr);

73IF n = 0 THEN

74RETURN [];

75END IF;

76RETURN quick_sort(arr, 0, n - 1);

77END; $$

78

79-- Example Usage:

80-- SELECT quick_sort_wrapper([10, 7, 8, 9, 1, 5]);

81-- SELECT quick_sort_wrapper([1]);

82-- SELECT quick_sort_wrapper([]);
Algorithm description viewbox

CQL: Implement Quick Sort

Algorithm description:

This Cassandra CQL implementation of Quick Sort uses a divide-and-conquer strategy. It selects a pivot element, partitions the list around the pivot (elements smaller than the pivot go to its left, larger elements to its right), and then recursively sorts the sub-lists. The `partition` helper function handles the in-place rearrangement. Quick Sort is generally efficient for large datasets, though its worst-case performance can be O(N^2).

Algorithm explanation:

Quick Sort works by selecting a pivot element from the list and partitioning the other elements into two sub-lists according to whether they are less than or greater than the pivot. The sub-lists are then sorted recursively. The `partition` function chooses the last element as the pivot, iterates through the list, and swaps elements smaller than the pivot to the left side. Finally, it places the pivot in its correct sorted position. The `quick_sort` function then recursively calls itself on the sub-lists. Average time complexity is O(N log N). Worst-case time complexity is O(N^2), occurring when the pivot selection consistently leads to unbalanced partitions (e.g., on an already sorted list with the last element as pivot). Space complexity is O(log N) on average due to recursion stack depth, and O(N) in the worst case. Edge cases handled: empty lists, single-element lists, and the recursive base case.

Pseudocode:

FUNCTION quick_sort(arr, low, high):
  IF low < high THEN
    pivot_index = partition(arr, low, high)
    quick_sort(arr, low, pivot_index - 1)
    quick_sort(arr, pivot_index + 1, high)
  END IF
  RETURN arr
END FUNCTION

FUNCTION partition(arr, low, high):
  pivot_value = arr[high]
  i = low - 1

  FOR j from low to high - 1:
    IF arr[j] <= pivot_value THEN
      i = i + 1
      SWAP arr[i] and arr[j]
    END IF
  END FOR

  SWAP arr[i + 1] and arr[high]
  RETURN i + 1
END FUNCTION

FUNCTION quick_sort_wrapper(arr):
  n = size of arr
  IF n == 0 THEN
    RETURN []
  END IF
  RETURN quick_sort(arr, 0, n - 1)
END FUNCTION