Sort

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

/*@Author: Alécio Gomes de Souza 2017-09-01 */

/*Percorre o vetor jogando o menor número para a primeira posição*/

void SelectionSort(int *v,int n){

printf("\n\nIniciando Selection Sort...\n\n");

int m,aux;

for(int i=0;i< n-1;i++){

m = i;

for(int j = i+1;j < n;j++){

if(v[j] < v[m])

m = j;

}

if(i != m){

aux = v[i];

v[i] = v[m];

v[m] = aux;

}

}

}

/*Ordena o vetor deslocando os elementos a partir de um ponto*/

void DirectInsert(int *v,int n){

printf("\n\nIniciando Inserção Direta...\n\n");

int i,j,aux;

for(i = 1;i < n; i++){

j = i-1;

aux = v[i];

while(j >= 0 && (v[j+1] < v[j]) ){

v[j+1] = v[j];

j--;

}

v[j+1] = aux;

}

}

/*Desloca elementos até ordenar o vetor*/

void BubbleSort(int *v,int n){

printf("\n\nIniciando BubbleSort...\n\n");

int i,j,troca,aux;

j = n-1;

do{

troca = 0;

for(i = 0; i < j; i++){

if(v[i] > v[i+1]){

aux = v[i];

v[i] = v[i+1];

v[i+1] = aux;

troca = 1;

}

}

j--;

}while(troca == 1);

}

/*Similar ao BubbleSort, porém ordena na ida e na volta*/

void ShakerSort(int *v,int n){

printf("\n\nIniciando ShakerSort...\n\n");

int l,r,troca,i,aux;

r = n-1;

l = troca = 0;

while(troca == 0 && l > r){

troca = 1;

for(i = l;i<r;i++){

if(v[i] > v[i+1]){

aux = v[i];

v[i] = v[i+1];

v[i+1] = aux;

troca = 0;

}

}

r--;

for(i = r;i>l;i--){

if(v[i] > v[i-1]){

aux = v[i];

v[i] = v[i-1];

v[i-1] = aux;

troca = 0;

}

}

l++;

}

}

/*Utiliza pivos para ordenar o vetor por partes até que esteja completamente ordenado (Recursivo)*/

void QuickSort(int *v,int l,int r){

//printf("\nIniciando QuickSort...\n");

int pv = l,i,j,aux;

for(i = l+1; i <= r; i++){

j = i;

if(v[j] < v[pv]){

aux = v[j];

while(j > pv){

v[j] = v[j-1];

j--;

}

v[j] = aux;

pv++;

}

}

if(pv-1 >= l) QuickSort(v,l,pv-1);

if(pv+1 <= r) QuickSort(v,pv+1,r);

}

/*QuickSort sem uso de recursão

- Adaptada de http://alienryderflex.com/quicksort/

*/

void QuickSortNR(int *v, int n) {

#define MAX_LEVELS 1000

int pv, beg[MAX_LEVELS], end[MAX_LEVELS], i = 0, L, R ;

beg[0] = 0;

end[0] = n;

while (i>=0){

L = beg[i];

R = end[i]-1;

if (L < R){

pv = v[L];

while (L<R){

while (v[R] >= pv && L < R) R--;

if (L < R) v[L++] = v[R];

while (v[L] <= pv && L < R) L++;

if (L < R) v[R--] = v[L];

}

v[L]=pv;

beg[i+1] = L+1;

end[i+1] = end[i];

end[i++] = L;

}

else{

i--;

}

}

}

/*Divide vetor em vetores menores até chegar em elementos sozinho e volta recursivamente organizando o vetor*/

void MergeSort(int *v, int l, int r){

int i,j,k,mtd,*temp;

if(l == r) return;

mtd = (l+r)/2;

MergeSort(v,l,mtd);

MergeSort(v,mtd+1,r);

i = l; j = mtd+1; k = 0;

temp = (int*) malloc(sizeof(int)*(r-l+1));

while(i < mtd+1 || j < r+1){

if(i == mtd+1){

temp[k] = v[j]; j++; k++;

}else{

if(j == r+1){

temp[k] = v[i]; i++; k++;

}else{

if(v[i] < v[j]){

temp[k] = v[i]; i++; k++;

}else{

temp[k] = v[j]; i++; k++;

}

}

}

}

for(i = l; i <= r; i++){

v[i] = temp[i-l];

}

free(temp);

}

/*Retornos: 0 - Crescente 1 - Decrescente 2 - Não ordenado */

int IsOrdered(int *v, int n){

int res = 0, change = 0;

for(int i = 0; i < n; i++){

if(i < (n-2)){

if(v[i] > v[i+1]){

res = 1;

if(i > 0){

return 2;

}

}

}

}

return res;

}

int main(void) {

srand (time(NULL));

int *v,n,i;

//Tamanho do vetor

n = 5;

v = (int *) malloc(n*sizeof(int));

//Cria vetor

for(int i=0;i<n;i++)

v[i]= rand() % 100+1;

printf("Vetor inicial:\n");

for(int i=0;i<n;i++)

printf("%d ",v[i]);

//SelectionSort(v,n);

//DirectInsert(v,n);

//BubbleSort(v,n);

//ShakerSort(v,n);

//QuickSort(v,0,(n-1));

QuickSortNR(v,n);

printf("\nVetor ordenado:\n");

for(int i=0;i<n;i++)

printf("%d ",v[i]);

int *vec = (int *) malloc(3*sizeof(int));

vec[0] = 3;

vec[1] = 2;

vec[2] = 1;

printf("\n\nOrdenado: %d",IsOrdered(v,n));

return 0;

}