Записки программиста Программирование и не только

15Сен/126

[Java] Сортировка пузырьком

Теории уже достаточно для того, чтобы начать делать всякое.
Попробуем реализовать простейшую сортировку.

Что такое сортировка пузырьком?
Это когда последовательно берется каждый элемент массива и "всплывается" на своё место пока не встретит более "легкий" элемент или конец массива.

Что для этого надо?
Для начала, нужно проходить по всему массиву:

for(int i = 0; i < arr.length; i++)

Ничего сложного, да?
Теперь надо каждый найденный элемент поднимать вверх.

for(int i = 1; i < arr.length; i++)	//внимание на начальный номер
					//связано это с тем, что сравниваем с "предыдущим" пузырьком
					//но индекса "-1" в массиве нет
{
	for(int j = i; j >= 1; j--)
	{
		//меняем элементы местами
		int a = arr[j];
		arr[j] = arr[j-1];
		arr[j-1] = a;
	}
}

Элементы "всплывают". Но чего-то не хватает... Точно, проверки - нужно ли вообще всплывать!

for(int i = 1; i < arr.length; i++)
{
	for(int j = i; (j >= 1) && (arr[j] < arr[j - 1]); j--)
	//ПОКА (arr[j] меньше arr[j-1]) И (в массиве еще есть элементы (j >= 0))
        {
                int a = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = a;
	}
}

Вот так вот.
Массив для проверки можно создать так:

int arr[] = {4, 7, 2, 9, 0, 1, 9, 12 ,56 ,78};

Но мы жешь программисты!
Так что воспользуемся готовой функцией random!

int arr[] = new inr[10];
for(int i = 0; i < arr.length; i++)
	arr[i] = Math.random();

В качестве домашнего задания попробуйте реализовать сортировку по убыванию.
Ну и на сложное - Гномью сортировку (gnome sort)

Комментарии (6) Пинги (0)
  1. 1. Массивы целых чисел не получается сделать рандомом.
    2. Гном через while не получается. Как в этой среде сделать пошаговую работу, чтоб он показывал — сейчас я делаю это?
    3. Count++ — какое у этой конструкции назначение? У меня она не работает.
    Утро кончилось.

    Пузырёк

    public class hello
    {
    public static void main (String[] args)
    {
    double mas[];
    mas=new double[20];
    for (int i=0; i<mas.length; i++)
    {
    mas[i]= Math.floor(Math.random()*100);
    System.out.println(mas[i]+" "); //пробел еще под вопросом, потому что результат записывается в этом случае в столбик
    }
    System.out.println();
    for (int i=1;i=1)&&(mas[j]<mas[j-1]); j—)
    {
    //count ++;
    double a=mas[j];
    mas[j]=mas[j-1];
    mas[j-1]=a;
    }
    }
    for (int i=0; i<mas.length; i++)
    {
    System.out.println(mas[i]+" ");
    }
    System.out.println();
    }
    }

    Убывание (разница в одном символе)

    public class hello
    {
    public static void main (String[] args)
    {
    double mas[];
    mas=new double[20];
    for (int i=0; i<mas.length; i++)
    {
    mas[i]= Math.floor(Math.random()*100);//((Math.random(1 to 100)*100)%1);
    System.out.println(mas[i]+" ");
    }
    System.out.println();
    for (int i=1;i=1)&&(mas[j]>mas[j-1]); j—)
    {
    //count ++;
    double a=mas[j];
    mas[j]=mas[j-1];
    mas[j-1]=a;
    }
    }
    for (int i=0; i<mas.length; i++)
    {
    System.out.println(mas[i]+" ");
    }
    System.out.println();
    }
    }

    Гном

    public class hello
    {
    public static void main (String[] args)
    {
    double mas[];
    mas=new double[10];
    for (int i=0; i<mas.length; i++)
    {
    mas[i]= Math.floor(Math.random()*100);//((Math.random(1 to 100)*100)%1);
    System.out.println(mas[i]+" ");
    }
    System.out.println();

    //гном
    for (int i=1; i<mas.length;)
    {
    if ( mas[i-1]<= mas[i] )
    {
    i++;
    }
    else
    {
    double a=mas[i];
    mas[i]=mas[i-1];
    mas[i-1]=a;
    i—;
    if (i==0 )
    {
    i=1;
    }
    }
    }

    for (int i=0; i<mas.length; i++)
    {
    System.out.println(mas[i]+" ");
    }
    System.out.println();
    }
    }

    • > 1. Массивы целых чисел не получается сделать рандомом.

      Надо привести тип возвращаемого рандомом значения к целому числу:
      mas[i]= (int)(Math.random()*100);

      > 2. Гном через while не получается. Как в этой среде сделать пошаговую работу, чтоб он показывал – сейчас я делаю это?

      Гном у тебя получился неправильным. Он не возвращается на позицию, с которой начал менять элемент.
      Для отладки надо сначала поставить бряк на строчку, где ты хочешь начать отладку. Ставится он путем клика в сером поле слева от нужной строчки. Ну, а потом надо нажать не Run, а Debug.

      > 3. Count++ – какое у этой конструкции назначение? У меня она не работает.

      Оно лишнее. Убрал.

    • У System.out есть две функции вывода.
      print() — просто выводит строчку.
      println() — выводит строку и делает переход на следующую.

  2. Собака программиста на F# очень похожа на собаку кодера OCaml с той лишь разницей, что выходит гулять из дома только через окно.

  3. Пузырек!

    public class BubbleSort {
    public int[] Sort(int[] array) {
    int j = 0;
    int CounterPairs = 0;
    while (true) {
    if (array[j] > array[j + 1]) {
    int q = array[j];
    array[j] = array[j + 1];
    array[j + 1] = q;
    CounterPairs = 0;
    } else {
    CounterPairs++;
    }
    j++;
    if (j == array.length — 1) {
    j = 0;
    }
    if (CounterPairs == array.length — 1)
    break;
    }
    return array;
    }
    }

    // @Test
    import org.junit.Test;
    import static org.hamcrest.Matchers.is;
    import static org.junit.Assert.assertThat;

    public class BubbleSortTest {
    @Test
    public void whenEnterEvenArrayThenSortArray() {
    BubbleSort sorter = new BubbleSort();
    int[] input = new int[] {11, -2, -7, 0, 10, 1};
    int[] result = sorter.Sort(input);
    int[] expect = new int[] {-7, -2, 0, 1, 10, 11};
    assertThat(result, is(expect));
    }

    @Test
    public void whenEnterOddArrayThenSortArray() {
    BubbleSort sorter = new BubbleSort();
    int[] input = new int[] {2, 1, 5, 4, 3};
    int[] result = sorter.Sort(input);
    int[] expect = new int[] {1, 2, 3, 4, 5};
    assertThat(result, is(expect));
    }
    }


Leave a comment

Нет обратных ссылок на эту запись.