Tue. Mar 19th, 2024

Sorting – Quick sort algorithm

Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.

Quicksort is a comparison sort, meaning that it can sort items of any type for which a “less-than” relation (formally, a total order) is defined. In efficient implementations it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting.

//Varianta I
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <stdlib.h>
using namespace std;

#define MAX 100


/////functie pt citirea datelor
int read_data(int *a)
{
	int i,n;
	printf("n=");scanf("%d",&n);
		for (i=0;i<n;i++)
		{
		printf("a[%d]=",i);
		scanf("%d",&a[i]);
		}
		return n;
}
////////funtctie pt tiparirea elementelor din tablou
void list(int *a,int n)
{
	int i;
	for (i=0;i<n;i++)
	printf("%d",a[i]);
	printf("\n");
}

/*******************************************************************************\
 * alegerea pivotului la mijloc. Se ordoneaza crescator din tabloul a secventa
 * cu elementele aflate intre indicii l si r
\*******************************************************************************/
void quicksort(int l ,int r,int *a)
{
	int i,j,p,tmp;
	
	i = l;
	j = r;
	p = a[(l + r) / 2];

	while(i <= j)
	{
		while(a[i] < p)
			i++;
		while(a[j] > p)
			j--;
		if(i <= j)
		{
			tmp = a[i];
			a[i] = a[j];
			a[j] = tmp;
			i++;
			j--;
		}
	}
	if(l < j)
		quicksort(l,j,a);
	if(i < r)
		quicksort(i,r,a);
}

void main()
{
	int i,n;
	int a[100];
	n = read_data(a);
	quicksort(0,n-1,a);
	list(a,n);
}

//Varianta II
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <stdlib.h>
using namespace std;

#define MAX 100


/////functie pt citirea datelor
int read_data(int *a)
{
	int i,n;
	printf("n=");scanf("%d",&n);
		for (i=0;i<n;i++)
		{
		printf("a[%d]=",i);
		scanf("%d",&a[i]);
		}
		return n;
}
////////funtctie pt tiparirea elementelor din tablou
void list(int *a,int n)
{
	int i;
	for (i=0;i<n;i++)
	printf("%d",a[i]);
	printf("\n");
}

/*******************************************************************************\
 * aflarea pivotului ca cel mai mare element dintre primele doua distincte
\*******************************************************************************/
int find_pivot(int l,int r,int *a)
{
	int i;

	for(i=1;i<r;i++)
		if(a[i] != a[i+1])
			if(a[i] < a[i+1])
				return i+1;
			else
				return i;
	return -1;
}

/*******************************************************************************\
 * imparte secventa initiala in doua subsecvente astfel incat orice element din
 * prima secventa sa fie mai mic decat valoarea pivotului iar orice element din
 * cea de a doua secventa sa fie mai mare sau egal cu pivotul
\*******************************************************************************/
int split(int l,int r,int *a,int pivot)
{
	int i,j,aux;
	i = 1;
	j = r;
	do
	{
		aux = a[i];
		a[i] = a[j];
		a[j] = aux;
		while(a[i] < pivot)
			i++;
		while(a[j] >= pivot)
			j--;
	}while(i < j);
	return i;
}

/*******************************************************************************\
 * quicksort: se alege pivotul,se imparte secventa in doua subsecvente si se or-
 * doneaza apoi fiecare in parte
\*******************************************************************************/
void quicksort(int l ,int r,int *a)
{
	int k,value;
	int index = find_pivot(l,r,a);

	if(index != -1)
	{
		value = a[index];
		k = split(l,r,a,value);
		quicksort(l,k-1,a);
		quicksort(k,r,a);
	}
}

void main()
{
	int i,n;
	int a[100];
	n = read_data(a);
	quicksort(0,n-1,a);
	list(a,n);
}

60,788 total views, 1 views today