Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Для новичков > Сортировка выбором


Автор: papochka 11.1.2010, 18:15
Привет. Осваиваю сортировку массивов.Остановился на сортировке выбором. Сначала искал инфу по ней, вроде нашел. Набросал код(ниже), но что-то оно выводит в том-же порядке как я и ввёл массив.. Помогите пож-ста, что не так?
И если можно, как я код для новичка оформляю.Можно неск. советов.
Спасибо.
С Ув. Игорь.


Код

#include <stdio.h>
#include <conio.h>

int main ()
{
    const int N = 10;
    int B,i,j,k;
    int A[N];
    printf("Vvod massiva: \n");
    for (i = 0; i < N; i++)
    {
        printf("A[%d]=\a",i);
        scanf("%d",&A[i]);
    }
    for ( i = 1; i < N; i++)
    {
        B = A[i];
    for  (j = 0; j < i; j++)
        if (B < A[j])
        {
            for (k = i - 1; k < j; k--)
                A[k + 1] = A[k];
        }

        A[i] = B;
    }
    printf("Sort Massiv: ");
    for (i = 0; i < N; i++)
    printf("%d ",A[i]);
    getch();
    return 0;
}

Автор: bsa 11.1.2010, 18:36
в строке 21 попробуй поставить условие k <= j
в строке 25 i замени на j

Автор: toxx 11.1.2010, 18:37
Маленько переделал...
Код

#include <stdio.h>
#include <conio.h>
int main ()
{
    const int N = 10;
    int B,i,j,k;
    int A[N],buf;
    printf("Vvod massiva: \n");
    for (i = 0; i < N; i++)
    {
        printf("A[%d]=\a",i);
        scanf("%d",&A[i]);
    }
    for ( i = 0; i < N-1; i++)
    {
    for  (j = i+1; j<N; j++)
        if (A[i] < A[j])
        {
            buf=A[i];
            A[i]=A[j];
            A[j]=buf;
        }
    }
    printf("Sort Massiv: ");
    for (i = 0; i < N; i++)
    printf("%d ",A[i]);
    getch();
    return 0;
}

Автор: comcon1 11.1.2010, 18:45
хихи, чувак, ты не маленько переделал. Ты превратил алгоритм в "пузырек".

Автор: toxx 11.1.2010, 18:49
Цитата(comcon1 @ 11.1.2010,  18:45)
хихи, чувак, ты не маленько переделал. Ты превратил алгоритм в "пузырек".

Неа, это сортировка выбором элемента

Вроде как выбираем элемент
Код

 for ( i = 0; i < N-1; i++)

И сравниваем поочередно
Код

 for  (j = i+1; j<N; j++)
        if (A[i] < A[j])


Блин или наврал чтото?)Так просто набросал, пузырек это вроде когда элемент самый большой вытесняют в конец массива?)

Автор: artsb 11.1.2010, 18:49
Код

        if (B < A[j])
        {
            for (k = i; k > j; k--)
                A[k] = A[k-1];
             A[j] = B; // это сюда
             break;  // и это ещё надо
        }


Добавлено через 2 минуты и 12 секунд
user posted image

Автор: papochka 11.1.2010, 18:53
Цитата(bsa @ 11.1.2010,  18:36)
в строке 21 попробуй поставить условие k <= j
в строке 25 i замени на j

Код

    if (B < A[j])

Вот это заменить? (20, на 21-й скобочка.)

Добавлено через 1 минуту и 36 секунд
Цитата(artsb @ 11.1.2010,  18:49)
Код

        if (B < A[j])
        {
            for (k = i; k > j; k--)
                A[k] = A[k-1];
             A[j] = B; // это сюда
             break;  // и это ещё надо
        }


Добавлено @ 18:52
user posted image

О, спасибо. Запарился немног))
Теперь понятно.

Автор: artsb 11.1.2010, 18:56
Цитата(papochka @  11.1.2010,  18:15 Найти цитируемый пост)
И если можно, как я код для новичка оформляю.Можно неск. советов.

Я бы так оформил:
Код

int main ()
{
 const int N = 10;
 int B,i,j,k;
 int A[N];
 printf("Vvod massiva: \n");

 for(i = 0; i < N; i++) {
  printf("A[%d]=\a", i);
  scanf("%d", &A[i]);
 }
 for(i = 1; i < N; i++) {
  B = A[i];
  for(j = 0; j < i; j++)
   if(B < A[j]) {
    for(k = i; k > j; k--)
     A[k] = A[k-1];
    A[j] = B;
    break;
   }
 }
 printf("Sort Massiv: ");

 for(i = 0; i < N; i++)
  printf("%d ", A[i]);

 getch();
 return 0;
}

Но тут, как говорится, на свой вкус и цвет. Каждый оформляет по-своему. Главное чтобы читабельно было ИМХО

Добавлено через 1 минуту и 57 секунд
Цитата(papochka @  11.1.2010,  18:53 Найти цитируемый пост)
Теперь понятно. 

Ещё на эту строку обратите внимание:
Код

for(k = i; k > j; k--)

Я в комментах про неё ничего не написал...

Автор: comcon1 11.1.2010, 19:08
toxx,  нет. Сортировка выбором, это поиск минимума и установка в начало, потом в оставшемся ищем минимум - и в начало. А у тебя двойной цикл, сравниваются попарно все элементы и меняются местами в сторону большего - это и есть пузырек (может он и называется не пузырек, но максимум там всплывает, нет, только что проверил - это пузырек).

Автор: Dov 11.1.2010, 19:10
Сортировка выбором - это нахождение в массиве минимального или максимального(если сортируем по убыванию) элемента (а иногда и того и другого, если сортировка двунаправленная) и обмен его с текущим элементом. И так до конца массива, исключая из поиска ранее отсортированные элементы.

Добавлено через 1 минуту и 9 секунд
comcon1 уже дал определение...   smile 

Автор: papochka 11.1.2010, 19:14
Спасибо.
Теперь ещё буду ковырять Быструю сортировку.)
Идея в том, что массив делится на два подмассива. В левую часть идёт элемент меньший, чем элемент в качестве среднего. В правую - больший.

Буду соображать, как сделать =)

Автор: toxx 11.1.2010, 19:16
Цитата(comcon1 @ 11.1.2010,  19:08)
toxx,  нет. Сортировка выбором, это поиск минимума и установка в начало, потом в оставшемся ищем минимум - и в начало. А у тебя двойной цикл, сравниваются попарно все элементы и меняются местами в сторону большего - это и есть пузырек (может он и называется не пузырек, но максимум там всплывает, нет, только что проверил - это пузырек).

Ошибочка значит вышла)Подзабыл уже сортировки)Вроде понатыкал, чето исправил, что аж переделал в другой метод оказывается=)

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)