#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;
}
