quicksort
// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
// @see https://www.youtube.com/watch?v=aXXWXz5rF64
// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
function partition(list, start, end) {
const pivot = list[end];
let i = start;
for (let j = start; j < end; j += 1) {
if (list[j] <= pivot) {
[list[j], list[i]] = [list[i], list[j]];
i++;
}
}
[list[i], list[end]] = [list[end], list[i]];
return i;
}
function quicksort(list, start = 0, end = undefined) {
if (end === undefined) {
end = list.length - 1;
}
if (start < end) {
const p = partition(list, start, end);
quicksort(list, start, p - 1);
quicksort(list, p + 1, end);
}
return list;
}
quicksort([5, 4, 2, 6, 10, 8, 7, 1, 0]);
0
8
#include<stdio.h>
int partition(int arr[], int low, int high) {
int temp;
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}
int print(int arr[], int n) {
for(int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
}
int main()
{
int n, i;
scanf("%d", &n);
int arr[n];
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
quick_sort(arr, 0, n - 1);
print(arr, n);
}
Thank you!
8
0
4.43
7
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p - 1)
quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo
for j := lo to hi do
if A[j] < pivot then
swap A[i] with A[j]
i := i + 1
swap A[i] with A[hi]
return i
Thank you!
7
0
4.38
8
/********** QuickSort(): sorts the vector 'list[]' **********/
/**** Compile QuickSort for strings ****/
#define QS_TYPE char*
#define QS_COMPARE(a,b) (strcmp((a),(b)))
/**** Compile QuickSort for integers ****/
//#define QS_TYPE int
//#define QS_COMPARE(a,b) ((a)-(b))
/**** Compile QuickSort for doubles, sort list in inverted order ****/
//#define QS_TYPE double
//#define QS_COMPARE(a,b) ((b)-(a))
void QuickSort(QS_TYPE list[], int beg, int end)
{
QS_TYPE piv; QS_TYPE tmp;
int l,r,p;
while (beg<end) // This while loop will substitude the second recursive call
{
l = beg; p = (beg+end)/2; r = end;
piv = list[p];
while (1)
{
while ((l<=r) && (QS_COMPARE(list[l],piv) <= 0)) l++;
while ((l<=r) && (QS_COMPARE(list[r],piv) > 0)) r--;
if (l>r) break;
tmp=list[l]; list[l]=list[r]; list[r]=tmp;
if (p==r) p=l;
l++; r--;
}
list[p]=list[r]; list[r]=piv;
r--;
// Select the shorter side & call recursion. Modify input param. for loop
if ((r-beg)<(end-l))
{
QuickSort(list, beg, r);
beg=l;
}
else
{
QuickSort(list, l, end);
end=r;
}
}
}
Thank you!
8
0
0
0
//I Love Java
import java.io.*;
import java.util.*;
import java.util.stream.*;
import static java.util.Collections.*;
import static java.util.stream.Collectors.*;
public class Quick_Sort_P {
static void swap(List<Integer> arr, int i, int j) {
int temp = arr.get(i);
arr.set(i, arr.get(j));
arr.set(j, temp);
}
static int partition(List<Integer> arr, int low, int high) {
int pivot = arr.get(high);
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr.get(j) < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
static void quickSort(List<Integer> arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static void main(String[] args) throws IOException {
BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
List<Integer> arr = Stream.of(buffer.readLine().replaceAll("\\s+$", "").split(" ")).map(Integer::parseInt)
.collect(toList());
int n = arr.size();
quickSort(arr, 0, n - 1);
System.out.println("Sorted array: ");
System.out.println(arr);
}
}
Thank you!
0
0
5
1
//last element selected as pivot
#include <iostream>
using namespace std;
void swap(int*,int*);
int partition(int arr[],int start,int end)
{
int pivot=arr[end];
int index=start;
int i=start;
while(i<end)
{
if(arr[i]<pivot)
{
swap(&arr[index],&arr[i]);
index++;
}
i++;
}
swap(&arr[end],&arr[index]);
return index;
}
void quicksort(int arr[],int start,int end)
{
if(start<end)
{
int pindex=partition(arr,start,end);
quicksort(arr,start,pindex-1);
quicksort(arr,pindex+1,end);
}
}
void display(int arr[],int n)
{
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
int main()
{
int n;
cout<<"enter the size of the array:"<<endl;
cin>>n;
int arr[n];
cout<<"enter the elements of the array:"<<endl;
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
cout<<"sorted array is:"<<endl;
quicksort(arr,0,n-1);
display(arr,n);
return 0;
}
void swap(int *a,int*b)
{
int temp=*a;
*a=*b;
*b=temp;
}
Thank you!
1
0
Are there any code examples left?
New code examples in category Other
-
Other 2023-03-27 22:50:10 how to select the whole line in vscode with keyboard shortcut
-
Other 2022-03-27 22:45:24 income of a web developer
-
Other 2022-03-27 22:35:01 \pyrcc_main.py: File does not exist 'resources.qrc'
-
Other 2022-03-27 22:30:45 rick roll embed code
-
Other 2022-03-27 22:20:08 Circuit_04_Potentiometer
-
Other 2022-03-27 22:20:05 iterative power
-
Other 2022-03-27 22:15:11 flutter run all
-
Other 2022-03-27 22:10:05 when is karlson release
-
Other 2022-03-27 22:10:02 wp .htaccess example
-
Other 2022-03-27 22:00:08 bash pause in file read line by line