Sortari

Selection Sort

Posted by Feroviarul on

Aspecte teoretice:

Selectia directã este una dintre cele mai simple metode de sortare si va lucra foarte bine pentru tabele mici, fiecare element (înregistrare), este mutat cel mult o datã.. Implementarea algoritmului este simplu.
Algoritmul presupune ca la fiecare pas “i “ sa se gaseasca elementul minim dintre a[i+1], a[i+2]…a[n] si se interschimba cu a[i].

Analiza complexității:

Se cheltuie cel mai mult timp cu cãutarea elementului minim din partea nesortatã a tabelei. Cãutarea se face de la stânga la dreapta. Pe parcursul fiecãrui pas este necesar o interschimbare, deci numãrul interschimbãrilor pentru N elemente este: N-1. Numãrul total al comparatiilor este proportional cu N^2. Timpul de executie al algoritmului este de ordinul O(N 2)în caz mediu si nefavorabil, chiar si când tabela este deja în ordine sortatã (crescãtoare). Este o metodã stabilã.

Exemplu Pas cu Pas:

5 6 1 2 4 3
1 6 5 2 4 3
1 2 5 6 4 3
1 2 3 6 4 5
1 2 3 4 6 5
1 2 3 4 5 6

Implementare:

Logo_C_Sharp
Cod Sursa C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace SelectionSortCS
{
    class Program
    {
        static void SelectionSort(int n, int [] v)
        {
            for (int i = 0; i < n; i++)
            {
                int max = i;
                int aux;
                for (int j = i + 1; j < n; j++)
                    if (v[max] > v[j])
                        max = j;
                aux = v[max];
                v[max] = v[i];
                v[i] = aux;
            }
        }
        static void Main(string[] args)
        {
            int n, i;
            int [] numere = new int[100];
            Console.WriteLine("Numarul de elemente n: ");
            n = Convert.ToInt32(Console.ReadLine());
            for (i = 0; i < n; i++)
            {
                Console.Write("Introduceti numarul #" + (i + 1) + " ");
                numere[i] = Convert.ToInt32(Console.ReadLine());
            }
            SelectionSort(n, numere);
            Console.WriteLine("Vectorul sortat este ");
            for (i = 0; i < n; i++)
                Console.Write(numere[i] + " ");
            Console.ReadLine();
        }
    }
}
Logo_VB
Cod Sursa VB
Module Module1
    Sub SelectionSort(ByVal n As Integer, ByVal v() As Integer)
        Dim i As Integer
        Dim j As Integer
        For i = 0 To n
            Dim max As Integer
            max = i
            Dim aux As Integer
            For j = i + 1 To n
                If v(max) > v(j) Then
                    max = j
                End If
            Next j
            aux = v(max)
            v(max) = v(i)
            v(i) = aux
        Next i
    End Sub
 
    Sub Main()
        Dim n, i As Integer
        Dim numere(100) As Integer
        Console.WriteLine("Numarul de elemente: ")
        n = Convert.ToInt32(Console.ReadLine())
        For i = 0 To n
            Console.Write("Introduceti numarul #" & (i + 1) & " ")
            numere(i) = Convert.ToInt32(Console.ReadLine())
        Next i
        SelectionSort(n, numere)
        Console.WriteLine("Vectorul sortat este ")
        For i = 0 To n
            Console.Write(numere(i) & " ")
        Next i
        Console.ReadLine()
    End Sub
 
End Module
Visual_C++_Icon
Cod Sursa C++
// SelectionSortCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include<conio.h>
 
using namespace std;
 
void SelectionSort(int n, int v[])
{
	for(int i=0;i<n;i++)
	{
		int max=i, aux;
		for(int j=i+1;j<n;j++)
			if(v[max]>v[j])
				max=j;
		aux=v[max];
		v[max]=v[i];
		v[i]=aux;
   }
}
 
int main()
{
	int n, i, numere[100];
	cout<<"Numarul de numere: ";cin>>n;
	for(i=0;i<n;i++)
	{
		cout<<"Introduceti numarul #"<<(i+1)<<": ";
		cin>>numere[i];
	}
	SelectionSort(n,numere);
	cout<<endl<<"Vectorul sortat:";
	for(i=0;i<n;i++)
		cout<<" "<<numere[i];
	system("pause");
}
phplogo
Cod Sursa PHP
<?php

 
function selection_sort($data)
{
	for($i=0; $i<count($data)-1; $i++) {
		$min = $i;
		for($j=$i+1; $j<count($data); $j++) {
			if ($data[$j]<$data[$min]) {
				$min = $j;
			}
		}
		$data = swap_positions($data, $i, $min);
	}
	return $data;
}
 
function swap_positions($data1, $left, $right) {
	$backup_old_data_right_value = $data1[$right];
	$data1[$right] = $data1[$left];
	$data1[$left] = $backup_old_data_right_value;
	return $data1;
}
$my_array = array(3, 0, 2, 5, -1, 4, 1);
echo "Vectorul original :\n";
echo implode(', ',$my_array );
echo "\nVectorul sortat :\n";
echo implode(', ',selection_sort($my_array)). PHP_EOL;
sleep(10);
?>
Java-Logo
Cod Sursa JAVA

 


//Complexitate: Nefavorabil: O(n^2); Mediu: O(n^2); Favorabil: O(n^2)class SelectionSortJAVA
{
  public static void SelectionSort(int n, int v[])
        {
            for (int i = 0; i < n; i++)
            {
                int max = I;
                int aux;
                for (int j = i + 1; j < n; j++)
                    if (v[max] > v[j])
                        max = j;
                aux = v[max];
                v[max] = v[i];
                v[i] = aux;
            }
        }        public static void main(String[] args)
        {
          int a[]={7,4,5,3,1,8,9,2,6,0};
          int i;
          SelectionSort(10,a);
          for (i=0;i<10;i++)
              System.out.println(a[i]+” “);
        }
}

 

Rezultat:

quicksortrezultat

 

Leave a comment