Algoritmos de ordenação

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

/*

startTime = (float)clock()/CLOCKS_PER_SEC;

endTime = (float)clock()/CLOCKS_PER_SEC;

timeElapsed = endTime - startTime;

*/

void selectionSort(int array[],int tam){

int i, j, min, aux;

float startTime,endTime,timeElapsed;

startTime = (float)clock()/CLOCKS_PER_SEC;

for (i = 0; i < (tam-1); i++)

{

min = i;

for (j = (i+1); j < tam; j++) {

if(array[j] < array[min])

min = j;

}

if (i != min) {

aux = array[i];

array[i] = array[min];

array[min] = aux;

}

}

endTime = (float)clock()/CLOCKS_PER_SEC;

timeElapsed = endTime - startTime;

printf("\t\t%f",timeElapsed);

}

void insertSort(int array[],int tam){

float startTime,endTime,timeElapsed;

startTime = (float)clock()/CLOCKS_PER_SEC;

int i, j, eleito;

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

eleito = array[i];

j = i - 1;

while ((j>=0) && (eleito < array[j])) {

array[j+1] = array[j];

j--;

}

array[j+1] = eleito;

}

endTime = (float)clock()/CLOCKS_PER_SEC;

timeElapsed = endTime - startTime;

printf("\t%f",timeElapsed);

}

void Merge(int *A,int *L,int leftCount,int *R,int rightCount) {

int i,j,k;

// i - to mark the index of left aubarray (L)

// j - to mark the index of right sub-raay (R)

// k - to mark the index of merged subarray (A)

i = 0; j = 0; k =0;

while(i<leftCount && j< rightCount) {

if(L[i] < R[j]) A[k++] = L[i++];

else A[k++] = R[j++];

}

while(i < leftCount) A[k++] = L[i++];

while(j < rightCount) A[k++] = R[j++];

}

void MergeSort(int *A,int n){

int mid,i, *L, *R;

if(n < 2) return; // base condition. If the array has less than two element, do nothing.

mid = n/2; // find the mid index.

// create left and right subarrays

// mid elements (from index 0 till mid-1) should be part of left sub-array

// and (n-mid) elements (from mid to n-1) will be part of right sub-array

L = (int*)malloc(mid*sizeof(int));

R = (int*)malloc((n- mid)*sizeof(int));

for(i = 0;i<mid;i++) L[i] = A[i]; // creating left subarray

for(i = mid;i<n;i++) R[i-mid] = A[i]; // creating right subarray

MergeSort(L,mid); // sorting the left subarray

MergeSort(R,n-mid); // sorting the right subarray

Merge(A,L,mid,R,n-mid); // Merging L and R into A as sorted list.

free(L);

free(R);

}

void opcaoMerge(int array[],int N){

int i,*merge;

merge = (int*)malloc(N*sizeof(int));

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

merge[i]=array[i];

}

float startTime,endTime,timeElapsed;

startTime = (float)clock()/CLOCKS_PER_SEC;

MergeSort(merge,N);

endTime = (float)clock()/CLOCKS_PER_SEC;

timeElapsed = endTime - startTime;

printf("\t%f",timeElapsed);

}

void quickSort(int *arr, int left, int right) {

int i = left, j = right;

int tmp;

int pivot = arr[(left + right) / 2];

/* partition */

while (i <= j) {

while (arr[i] < pivot)

i++;

while (arr[j] > pivot)