I want to review all the basic algorithms very quick and start to study harder algorithms and solve more difficult problems, and improve my algorithm skills in the end. So I will start to work on this from today, hoping I won’t give up..
quick sort is like continuously switching two elements from head and tail of the list until two pointers meet, and we do this recursively until the length of the list is 1.
$C++\ method:$
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int q[N];
int n;
void quick_sort(int l, int r)
{
if(l>=r) return;
int x = q[l + r >> 1];
int i = l - 1, j = r + 1;
while(i<j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if(i < j) swap(q[i], q[j]);
}
quick_sort(l, j);
quick_sort(j + 1, r);
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> q[i];
}
quick_sort(0, n-1);
for(int i = 0; i < n; i++)
{
cout << q[i] << " ";
}
return 0;
}
$Python method:$
def quick_sort(q,l,r):
if l>=r:
return
x=q[(l+r)//2]
i,j=l-1,r+1
while i<j:
while True:
i+=1
if q[i]>=x:
break
while True:
j-=1
if q[j]<=x:
break
if i<j:
q[i],q[j]=q[j],q[i]
quick_sort(q,l,j)
quick_sort(q,j+1,r)
if __name__=="__main__":
n=int(input())
q=list(map(int,input().split()))
quick_sort(q,0,n-1)
for i in q:
print(i,end=" ")