Метод сортировки выбором -2

@utwo · Регистрация: 10.10.2009

Author24 — интернет-сервис помощи студентам

Доброе время суток,
Чтоб не засорять чужую тему с чужими задачи, решил создать новую.

Используя сортировку выбором необходимо выбрать мин. элемент в массиве, перенести в вых. массив на очередную позицию. Во вход. массиве все элементы от следующего за текущим до конца сдвинуть на 1 влево.

Насколько я понял это должно выглядеть следующим образом (A-вход.массив, А"-выход.массив):

Код

           A=13,11,8,0,3,      A"=
           A=13,11,8,3,        A"=0
           A=13,11,8,          A"=0,3
           A=13,11,            A"=0,3,8
           A=13,               A"=0,3,8,11
           A=,                 A''=0,3,8,11,13

В соседней теме выложили листинг. Но похоже это не много не мой мой вариант.

C++

#include <iostream>
#include <string>
 
using namespace std;
 
 
 
void selectSort(string a[], long size) {
        long i, j, k;
        string x;
 
        for( i=0; i < size; i++) { // i - номер текущего шага
                k=i; x=a[i];
                for( j=i+1; j < size; j++) // цикл выбора наименьшего элемента
                        if ( a[j] < x ) {
                                k=j; x=a[j]; // k - индекс наименьшего элемента
                        }
                        a[k] = a[i]; a[i] = x; // меняем местами наименьший с a[i]
        }
}
 
 
void main()
{ 
        int n, A=10, B=55;
        
 
        cout<<"enter n:"; cin>>n;
        string *s=new string[n];
        for (int i=0; i<n; i++)
        {
                cout<<i+1<<":"; cin>>s[i];
        }
 
        selectSort(s,n);
 
        for (int i=0; i<n; i++)
        {
                cout<<s[i]<<endl;
        }
        cout<<endl; system("pause");
}

Спасибо за любую информацию!

valeriikozlov · 10.10.2009, 07:09

Сообщение от utwo

Используя сортировку выбором необходимо выбрать мин. элемент в массиве, перенести в вых. массив на очередную позицию. Во вход. массиве все элементы от следующего за текущим до конца сдвинуть на 1 влево.

Для такого условия код:

C++

#include<iostream.h>
#include<windows.h>
#include <process.h> 
int *mas1, *mas2, n, i, j, size, min, min_poz;
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    cout<<"Ââåäèòå êîëè÷åñòâî ÷èñåë"<<endl;
    cin>>n;
    size=n;
    // ñîçäàåì âõîäíîé è âûõîäíîé äèíàìè÷åñêèå ìàññèâû è îáíóëÿåì èõ ýëåìåíòû
    mas1= new int[n];
    mas2= new int [n];
    for(i=0; i<n; i++)
        mas1[i]=mas2[i]=0;
    // çàïîëíÿåì ÷èñëàìè âõîäíîé ìàññèâ
    cout<<"Ââåäèòå ÷èñëà âõîäíîãî ìàññèâà"<<endl;
    for(i=0; i<n; i++)
    {
        cout<<i+1<<" = ";
        cin>>mas1[i];
        cout<<endl;
    }
    // âûáîðî÷íàÿ ñîðòèðîâêà
    j=0;    
    while(n!=1)
    {
        min=mas1[0];
        min_poz=0;
        for(i=0; i<n; i++)
            if(min>mas1[i])
            {
                min=mas1[i];
                min_poz=i;
            }
        mas2[j]=mas1[min_poz];
        j++;
        for(i=min_poz; i<n-1; i++)
            mas1[i]=mas1[i+1];
        n--;
    }
    mas2[j]=mas1[0];
// âûâîä îòñîðòèðîâàííîãî ìàññèâà íà ýêðàí
    cout<<endl<<endl<<"Îòñîðòèðîâàííûé ìàññèâ"<<endl;
    for(i=0; i<size; i++)
        cout<<i+1<<" = "<<mas2[i]<< endl;   
    system("pause");
    return 0;
}

А ввобще-то выборочная сортировка не обязательно проводится с использованием двух массивов (входного и выходного). Обычно она проводится прямо в неотсортированном массиве.

@utwo · 07.11.2009, 11:20 **[ТС]**

Теперь буду усложнять задачку

Задачку нужно выполнить в виде функции, использующую для работы со строкой только указатели и операции вида *р++, Р++ и т.д. Строку, которую возвращает функция необходимо также сделать через указатель.

Данная функция будет находит мин. элемент массива и возвращает указатель на него. С использованием этой функции реализовать сортировку выбором.

Спасибо!

valeriikozlov · 07.11.2009, 11:41

utwo, Вам сделать на базе Вашего кода (с использованием двух массивов (входного и выходного)) или более оптимальный вариант (с использованием только одного массива)?

@utwo · 07.11.2009, 11:46 **[ТС]**

Сообщение от valeriikozlov

utwo, Вам сделать на базе Вашего кода (с использованием двух массивов (входного и выходного)) или более оптимальный вариант (с использованием только одного массива)?

Два массива необходимо было только для наглядности. В данном случае пытаюсь переделать прежний код, но с одним массивом.

valeriikozlov · 07.11.2009, 12:07

Два массива необходимо было только для наглядности. В данном случае пытаюсь переделать прежний код, но с одним массивом.

Вот с одним массивом Ваш код:

C++

#include<iostream.h>
#include<windows.h>
#include <process.h> 
int *mas1, n, i, j, temp, size, min_poz;
int main()
{
        SetConsoleCP(1251);
        SetConsoleOutputCP(1251);
        cout<<"Ââåäèòå êîëè÷åñòâî ÷èñåë"<<endl;
        cin>>n;
        size=n;
        // ñîçäàåì âõîäíîé è âûõîäíîé äèíàìè÷åñêèå ìàññèâû è îáíóëÿåì èõ ýëåìåíòû
        mas1= new int[n];
        // çàïîëíÿåì ÷èñëàìè âõîäíîé ìàññèâ
        cout<<"Ââåäèòå ÷èñëà âõîäíîãî ìàññèâà"<<endl;
        for(i=0; i<n; i++)
        {
                cout<<i+1<<" = ";
                cin>>mas1[i];
                cout<<endl;
        }
        // âûáîðî÷íàÿ ñîðòèðîâêà
        while(n!=1)
        {
                min_poz=size-n;
                for(i=size-n; i<size; i++)
                    if(mas1[min_poz]>mas1[i])
                       min_poz=i;
                temp=mas1[size-n];
                mas1[size-n]=mas1[min_poz];
                mas1[min_poz]=temp;
                n--;
        }
 // âûâîä îòñîðòèðîâàííîãî ìàññèâà íà ýêðàí
        cout<<endl<<endl<<"Îòñîðòèðîâàííûé ìàññèâ"<<endl;
        for(i=0; i<size; i++)
                cout<<i+1<<" = "<<mas1[i]<< endl;       
        system("pause");
        return 0;
}

Под эти условия нужно переделать?:

Задачку нужно выполнить в виде функции, использующую для работы со строкой только указатели и операции вида *р++, Р++ и т.д. Строку, которую возвращает функция необходимо также сделать через указатель.

Данная функция будет находит мин. элемент массива и возвращает указатель на него. С использованием этой функции реализовать сортировку выбором.

@utwo · 07.11.2009, 19:46 **[ТС]**

Сообщение от valeriikozlov

Под эти условия нужно переделать?:

Да, хотя бы направить на путь истинный, в какую сторону копать

valeriikozlov · 07.11.2009, 20:00

C++

#include<iostream.h>
#include<windows.h>
#include <process.h> 
int *mas1, n, i, j, temp, size, min_poz, *pMas;
int main()
{
        SetConsoleCP(1251);
        SetConsoleOutputCP(1251);
        cout<<"Ââåäèòå êîëè÷åñòâî ÷èñåë"<<endl;
        cin>>n;
        size=n;
        // ñîçäàåì âõîäíîé è âûõîäíîé äèíàìè÷åñêèå ìàññèâû è îáíóëÿåì èõ ýëåìåíòû
        mas1= new int[n];
        // çàïîëíÿåì ÷èñëàìè âõîäíîé ìàññèâ
        cout<<"Ââåäèòå ÷èñëà âõîäíîãî ìàññèâà"<<endl;
        pMas=mas1;
        for(i=0; i<n; i++)
        {
                cout<<i+1<<" = ";
                cin>>*(pMas+i);
                cout<<endl;
        }
        // âûáîðî÷íàÿ ñîðòèðîâêà
        while(n!=1)
        {
                min_poz=size-n;
                for(i=size-n; i<size; i++)
                    if(*(pMas+min_poz)>*(pMas+i))
                       min_poz=i;
                                temp=*(pMas+size-n);
                                *(pMas+size-n)=*(pMas+min_poz);
                                *(pMas+min_poz)=temp;
                n--;
        }
 // âûâîä îòñîðòèðîâàííîãî ìàññèâà íà ýêðàí
        cout<<endl<<endl<<"Îòñîðòèðîâàííûé ìàññèâ"<<endl;
        for(i=0; i<size; i++)
                cout<<i+1<<" = "<<*(pMas+i)<< endl;       
        system("pause");
        return 0;
}

@utwo 3 / 3 / 0 Регистрация: 10.10.2009 Сообщений: 108
	07.11.2009, 11:20 [ТС]	3
	Теперь буду усложнять задачку Задачку нужно выполнить в виде функции, использующую для работы со строкой только указатели и операции вида *р++, Р++ и т.д. Строку, которую возвращает функция необходимо также сделать через указатель. Данная функция будет находит мин. элемент массива и возвращает указатель на него. С использованием этой функции реализовать сортировку выбором. Спасибо! 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	07.11.2009, 11:41	4
	utwo, Вам сделать на базе Вашего кода (с использованием двух массивов (входного и выходного)) или более оптимальный вариант (с использованием только одного массива)? 1

@utwo 3 / 3 / 0 Регистрация: 10.10.2009 Сообщений: 108
	07.11.2009, 11:46 [ТС]	5
	Сообщение от valeriikozlov utwo, Вам сделать на базе Вашего кода (с использованием двух массивов (входного и выходного)) или более оптимальный вариант (с использованием только одного массива)? Два массива необходимо было только для наглядности. В данном случае пытаюсь переделать прежний код, но с одним массивом. 0

@utwo 3 / 3 / 0 Регистрация: 10.10.2009 Сообщений: 108
	07.11.2009, 19:46 [ТС]	7
	Сообщение от valeriikozlov Под эти условия нужно переделать?: Да, хотя бы направить на путь истинный, в какую сторону копать 0

	07.11.2009, 20:00