Сортировки. Help!

Discussion in 'С/С++, C#, Rust, Swift, Go, Java, Perl, Ruby' started by nc.STRIEM, 7 Dec 2006.

  1. nc.STRIEM

    nc.STRIEM Members of Antichat

    Joined:
    5 Apr 2006
    Messages:
    1,036
    Likes Received:
    347
    Reputations:
    292
    Нужны 2 функции сортировки, написанные на С++ по следующим алгоритмам:

    - Обменная сортировка с разделением
    - Сортировка слиянием

    Может у кого завалялись где, буду очень благодарен!
    Нужно очень срочно (конкретно сегодня), самому писать прост нет времени.
     
    #1 nc.STRIEM, 7 Dec 2006
    Last edited: 7 Dec 2006
  2. TaNkist

    TaNkist Elder - Старейшина

    Joined:
    6 Apr 2006
    Messages:
    147
    Likes Received:
    47
    Reputations:
    19
    Сортировка с разделением
    Code:
    #include "iostream.h"
    #include "stdio.h"
    
    void quickSort( int *array, int L, int R ){
    int i, j;
    int item, temp;
    	i = L;
    	j = R;
    	item = array[(L + R)/2];
    	while ( i <= j ){
    		while ( array[i] < item ) i++;
    		while ( item < array[j] ) j--;
    		if ( i <= j ){ 
    			temp = array[i];
    			array[i] = array[j];
    			array[j] = temp;
    			i++;
    			j--;
    		}
    	}
    	if ( L < j ) quickSort( array, L, j );
    	if ( i < R ) quickSort( array, i, R );
    }
    
    void main(){
    	int i, size;
    	int *array;
        cout << "Quick Sort.\nEnter array dimension: ";
        cin >> size;
    	array = new int[size];
        cout << "Enter " << size << " elements: ";
    	for ( i = 0; i < size; i ++ ){
    		cin >> array[i];
    	}
    
    	quickSort( array, 0, size - 1 );
    
    	cout << "Your array after sorting: ";
    	for ( i = 0; i < size; i ++ ){
    		cout << array[i] << " ";
    	} 
        cout << "\nPress \"Enter\" to continue..." << endl; 
        getchar();
    }
    
    Сортировка слиянием
    Code:
    template<class T>
    void merge(T a[], long lb, long split, long ub) {
    // Слияние упорядоченных частей массива в буфер temp
    // с дальнейшим переносом содержимого temp в a[lb]...a[ub]
    
      // текущая позиция чтения из первой последовательности a[lb]...a[split]
      long pos1=lb;
    
      // текущая позиция чтения из второй последовательности a[split+1]...a[ub]
      long pos2=split+1;
    
      // текущая позиция записи в temp
      long pos3=0;  
    
      T *temp = new T[ub-lb+1];
    
      // идет слияние, пока есть хоть один элемент в каждой последовательности
      while (pos1 <= split && pos2 <= ub) {
        if (a[pos1] < a[pos2])
          temp[pos3++] = a[pos1++];
        else
          temp[pos3++] = a[pos2++];
      }
    
      // одна последовательность закончилась - 
      // копировать остаток другой в конец буфера 
      while (pos2 <= ub)   // пока вторая последовательность непуста 
        temp[pos3++] = a[pos2++];
      while (pos1 <= split)  // пока первая последовательность непуста
        temp[pos3++] = a[pos1++];
    
      // скопировать буфер temp в a[lb]...a[ub]
      for (pos3 = 0; pos3 < ub-lb+1; pos3++)
        a[lb+pos3] = temp[pos3];
    
      delete temp[ub-lb+1];
    }
    
    Не уверен, что это точно такие сортировки, какие тебе нужны. Посмотри еще http://algolist.manual.ru/sort/
     
    1 person likes this.
  3. Dronga

    Dronga ВАША реклама ТУТ!!

    Joined:
    1 Jul 2005
    Messages:
    575
    Likes Received:
    239
    Reputations:
    249
    Найди на последнем DVD-хакера, который 9Гб, там все алгоритмы сортировок на С и на Pascal. У кого есть, выложите где-нить, многим пригодится, линк сюда.
     
Loading...