Scribd
Upload
11 views6 pages

Selection Sort Algorithm Overview

The document provides an overview of various sorting algorithms, including their time complexities: Bubble sort, Selection sort, Insertion sort, Quicksort, and Mergesort. It includes code snippets for each algorithm, demonstrating their implementation in Java. Additionally, it mentions graph algorithms such as Prim's and Dijkstra's algorithms.

Uploaded by

pablolope997
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views6 pages

Selection Sort Algorithm Overview

The document provides an overview of various sorting algorithms, including their time complexities: Bubble sort, Selection sort, Insertion sort, Quicksort, and Mergesort. It includes code snippets for each algorithm, demonstrating their implementation in Java. Additionally, it mentions graph algorithms such as Prim's and Dijkstra's algorithms.

Uploaded by

pablolope997
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

ADSW

COMPLEJIDAD

ALGORITMOS DE ORDENACIÓN
• Bubble sort: O(n2)
• Selection sort: O(n2)
• Insertion sort: O(n2)
• Quicksort: O(n2)
• Mergesort: O(n log n)

Visitar enlace para ver cómo funciona cada algoritmo de ordenación:


[Link]

GRAFOS
• Algoritmo de Prim
• Algoritmo de Dijkstra
BUBBLE SORT O(n2)
@Override
public void sort (String[ ] data) {
boolean changed;
do{
changed=false;
for (int i=0; i<[Link]-1; i++) {
if (data[i].compareTo(data[i+1])>0) {
swap(data, i, i+1);
changed=true;
}
}
} while (changed);
}
private void swap (String[ ] data, int i, int j) {
if (i==j)
return;
String si=data[i];
String sj=data[j];
data[i]=sj;
data[j]=si;
}
SELECTION SORT O(n2)
@Override
public void sort (String [ ] data) {
for (int i=0; i<[Link]-1; i++) {
int j=min(data, i, [Link]);
swap(data, i, j);
assert sorted(data, 0, i+1);
}
}

private int min (String [ ] data, int a, int z) {


int m=a;
for (int i=a; i<z; i++) {
if (data[i].compareTo(data[m]) <0 )
m=i;
}
return m;
}
INSERTION SORT O(n2)
@Override
public void sort (String[ ] data) {
for (int i=1; i<[Link]; i++) {
insert (data, I, data[i]);
assert sorted (data, 0, i+1);
}
}
Private void insert (String[ ] data, int z, String v) {
int j=z;
while (0<j && [Link](data[j-1]) < 0)
j--;
[Link](data, j, data, j+1, z-j);
data[j]=v;
}
QUICKSORT O(n2)
private void sort (String[ ] data, int a, int z) {
if (z<=a)
return;
String pivot=data[a];
int i=a;
for (int j=a+1; j<z; j++) {
if (data[j].compareTo(pivot)) < 0) {
i++;
swap (data, i, j);
}
}
swap (data, a, i);
sort (data, a, i);
sort (data, i+1, z);
}
private void swap (String[ ] data, int i, int j) {
if (i==j)
return;
String si=data[i];
String sj=data[j];
data[i]=sj;
data[j]=si;
}
MERGESORT RECURSIVO O (n log n)
@Override
public void sort (String[ ] data) {
List <String> list = new ArrayList<>( );
[Link](list, data);
sort (list);
[Link] (data);
}
private void sort (List<String> list) {
if ([Link]( ) < 2)
return;
int m = [Link]( ) / 2;
List<String> left = new ArrayList<>([Link] (0, m));
List<String> right = new ArrayList<>([Link](m, [Link]( )));
sort (left);
sort (right);
[Link]( );
while ([Link]( ) > 0 && [Link]( ) > 0) {
String sl = [Link](0);
String sr = [Link](0);
if ([Link](sr) < 0)
[Link]([Link](0));
else
[Link]([Link](0));
}
while ([Link]( ) > 0)
[Link]([Link](0));
while ([Link]( ) > 0)
[Link]([Link](0));
}

You might also like