USE GNU PROLOG! Reimplement the Quicksort. In the given example, the first (left-most) element of the given list is selected as the pivot. In this question, you must choose the second element of the list as the pivot. Hint: You can represent the input list into pairs: [First | [Pivot | Tail]]. You must write comments to indicate the size-n problem, stopping condition and its return value, size m-problems, and construction of the size-n problem from size-m problems. Test case: | ?- qsort2([8, 3, 4, 12, 25, 4, 6, 1, 9, 22, 6], Sorted). It returns: Sorted = [1,3,4,4,6,6,8,9,12,22,25]
USE GNU PROLOG!
Reimplement the Quicksort. In the given example, the first (left-most) element of the given list is selected as the pivot. In this question, you must choose the second element of the list as the pivot.
Hint: You can represent the input list into pairs: [First | [Pivot | Tail]]. You must write comments to indicate the size-n problem, stopping condition and its return value, size m-problems, and construction of the size-n problem from size-m problems.
Test case:
| ?- qsort2([8, 3, 4, 12, 25, 4, 6, 1, 9, 22, 6], Sorted). It returns:
Sorted = [1,3,4,4,6,6,8,9,12,22,25]
![qsort(,) :-!.
% empty list is already sorted
qsort([Pivot Tail], Sorted):- % Take first number as pivot
split(Pivot, Tail, L1, L2),
Quick Sort Code in Prolog
% sort first part
% sort second part
append(Sorted 1, [Pivot|Sorted2], Sorted).
split(,0,0,0).
qsort(L1, Sorted1),
qsort(L2, Sorted2),
CSE240
11/19/2002
split(Pivot,[X|T],[X|Le],Gt):-
split(Pivot,
X=<Pivot, split(Pivot, T,Le, Gt).
[X|T],Le,[X|Gt]):-
X > Pivot, split(Pivot, T,Le, Gt).
|| 2- [quicksort).
compiling /afs/asu.edu/users/y
/afs/asu.edu/users/y/c/h/ychen
980 bytes written, 7 ms
yes
?- qsort ([3, 2,5, 3, 1], S).
S = [1,2,3,3,5) ?
% stopping condition
% take first from Tail
% and put it into Le
% take first from Tail
% and put it into Gt
Ch 5
4](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fcede8746-e52f-4eaf-bfc2-0cf286297e7e%2F8128e9ff-f57e-4982-afc9-66689a33c2c9%2Fl28m0rj_processed.png&w=3840&q=75)
Here's the implementation of Quicksort with the second element of the list as the pivot:
CODE:
% Quicksort with second element as pivot
qsort2([], []). % base case: empty list, return empty list
qsort2([X], [X]). % base case: single element list, return the same list
qsort2([First, Pivot | Tail], Sorted) :-
% Divide the list into two sublists based on the pivot
partition(Pivot, [First|Tail], Left, Right),
% Recursively sort the two sublists
qsort2(Left, SortedLeft),
qsort2(Right, SortedRight),
% Combine the sorted sublists and the pivot
append(SortedLeft, [Pivot|SortedRight], Sorted).
% Helper predicate to partition a list into two sublists
% based on a pivot element
partition(_, [], [], []).
partition(Pivot, [X|Xs], [X|Left], Right) :-
X =< Pivot,
partition(Pivot, Xs, Left, Right).
partition(Pivot, [X|Xs], Left, [X|Right]) :-
X > Pivot,
partition(Pivot, Xs, Left, Right).
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
