Programas/Shell Sort at master · GGLSoftware/Programas · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h>
#include <stdlib.h>
#define Nodo struct nodo

Nodo{
	int dato;
	Nodo*siguiente;
	Nodo*anterior;
};

void Insertar(int dato);
void visualizarLista();
void shellSort(int N);
void cambiarAtras(Nodo*piv,int inter);
Nodo*inicio=NULL;
Nodo*final=NULL;

int main(){
	int N,dato,i;
	printf("No. de datos:");
	scanf("%i",&N);
	for(i=0;i<N;i++){
		scanf("%i",&dato);
		Insertar(dato);
	}
	shellSort(N);
	printf("Lista Ordenada:\n");
	visualizarLista();
}

void shellSort(int N){
	int inter=N/2;
	Nodo*piv,*aux;
	while(inter>0){
		piv=aux=inicio;
		int cont=0;
	    while(cont!=inter){
		aux=aux->siguiente;
		cont++;
	    }
		while(aux!=NULL){
	    if(piv->dato>aux->dato){
			   int temp=piv->dato;
			   piv->dato=aux->dato;
			   aux->dato=temp;
			   cambiarAtras(piv,inter);
		}
		aux=aux->siguiente;
		piv=piv->siguiente;
        }
        inter=inter/2;
	}
}

void cambiarAtras(Nodo*piv,int inter){
	int cont=0;
	Nodo*aux=piv;
	while(cont!=inter && aux!=NULL){
		aux=aux->anterior;
		cont++;
	}
	if(aux==NULL)
	return;
	if(piv->dato<aux->dato){
		int temp=piv->dato;
		piv->dato=aux->dato;
		aux->dato=temp;
		cambiarAtras(aux,inter);
	}else{
		return;
	}
}

void Insertar(int dato){
	Nodo*aux=inicio;
	Nodo*nuevo=(Nodo*)malloc(sizeof(int));
	nuevo->dato=dato;
	nuevo->siguiente=NULL;
	nuevo->anterior=NULL;
	if(inicio==NULL){
		inicio=nuevo;
		final=nuevo;
	}else{
		final->siguiente=nuevo;
		nuevo->anterior=final;
		final=nuevo;
	}
}

void visualizarLista(){
	Nodo*aux=inicio;
	while(aux!=NULL){
		printf("%i ",aux->dato);
		aux=aux->siguiente;
	}
}