كيف يمكنني فرز قائمة من الأعداد الصحيحة باستخدام إضافية واحدة فقط صحيح متغير ؟

Question

كيفية فرز قائمة من القيم باستخدام واحد فقط متغير ؟

تحرير:وفقا @ايغور تعليق انا ليصبح السؤال.

Answer 1

حل في C:

#include <stdio.h>

int main()
{
    int list[]={4,7,2,4,1,10,3};
    int n;  // the one int variable

    startsort:
    for (n=0; n< sizeof(list)/sizeof(int)-1; ++n)
        if (list[n] > list[n+1]) {
            list[n] ^= list[n+1];
            list[n+1] ^= list[n];
            list[n] ^= list[n+1];
            goto startsort;
        }

    for (n=0; n< sizeof(list)/sizeof(int); ++n)
        printf("%d\n",list[n]);
    return 0;
}

الإخراج هو بالطبع نفس أيقونة البرنامج.

Answer 2

وأظن أنا أقوم بالواجبات المنزلية الخاصة بك بالنسبة لك, ولكن مهلا انها مثيرة للاهتمام والتحدي.هنا الحل في رمز:

procedure mysort(thelist)
    local n # the one integer variable
    every n := (1 to *thelist & 1 to *thelist-1) do
    if thelist[n] > thelist[n+1] then thelist[n] :=: thelist[n+1]
    return thelist
end

procedure main(args)
    every write(!mysort([4,7,2,4,1,10,3]))
end

الإخراج:

1
2
3
4
4
7
10

Answer 3

هل يمكن أن تولد/كتابة الكثير من الفرز-الشبكات لكل من الممكن حجم القائمة.داخل الفرز الشبكة يمكنك استخدام متغير واحد عن عملية مقايضة.

لا نوصي أن يمكنك القيام بذلك في البرنامج, ولكن من الممكن مع ذلك.

وهنا الفرز الروتينية لجميع ن تصل إلى 4 في ج

// define a compare and swap macro 
#define order(a,b) if ((a)<(b)) { temp=(a); (a) = (b); (b) = temp; }

static void sort2 (int *data)
// sort-network for two numbers
{
  int temp;
  order (data[0], data[1]);
}

static void sort3 (int *data)
// sort-network for three numbers
{
  int temp;
  order (data[0], data[1]);
  order (data[0], data[2]);
  order (data[1], data[2]);
}

static void sort4 (int *data)
// sort-network for four numbers
{
  int temp;
  order (data[0], data[2]);
  order (data[1], data[3]);
  order (data[0], data[1]);
  order (data[2], data[3]);
  order (data[1], data[2]);
}

void sort (int *data, int n)
{
  switch (n)
    {
    case 0:
    case 1:
      break;
    case 2:
      sort2 (data);
      break;
    case 3:
      sort3 (data);
      break;
    case 4:
      sort4 (data);
      break;
    default:
      // Sorts for n>4 are left as an exercise for the reader
      abort();
    }
}

من الواضح أنك تحتاج إلى الفرز-شبكة رمز لكل من الممكن N.

مزيد من المعلومات هنا:

http://en.wikipedia.org/wiki/Sorting_network

Answer 4

في جاوة:

import java.util.Arrays;

/**
 * Does a bubble sort without allocating extra memory
 *
 */
public class Sort {
    // Implements bubble sort very inefficiently for CPU but with minimal variable declarations
    public static void sort(int[] array) {
        int index=0;
        while(true) {
            next:
            {
                // Scan for correct sorting. Wasteful, but avoids using a boolean parameter
                for (index=0;index<array.length-1;index++) {
                    if (array[index]>array[index+1]) break next;
                }
                // Array is now correctly sorted
                return;
            }
            // Now swap. We don't need to rescan from the start
            for (;index<array.length-1;index++) {
                if (array[index]>array[index+1]) {
                    // use xor trick to avoid using an extra integer
                    array[index]^=array[index+1];
                    array[index+1]^=array[index];
                    array[index]^=array[index+1];
                }
            }
        }
    }

    public static void main(final String argv[]) {
        int[] array=new int[] {4,7,2,4,1,10,3};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
}

في الواقع باستخدام خدعة المقترحة من قبل نيلز, يمكنك القضاء على حتى واحد ما تبقى الباحث تخصيص - على الرغم من وبطبيعة الحال من شأنه أن يضيف إلى كومة بدلا من ذلك...

Answer 5

في روبي:[1, 5, 3, 7, 4, 2].نوع

Answer 6

لا, هو بالفعل فرز.(كما في مسألة غامضة ، سأفترض متغير مرادف كائن)

Answer 7

إذا كان لديك قائمة (1 5 3 7 4 2) و متغير v, يمكنك تبادل اثنين من القيم القائمة ، على سبيل المثال 3 و 7, من أول تعيين 3 v, ثم تعيين 7 إلى المكان من 3 ، وأخيرا تعيين قيمة v إلى المكان الأصلي 7.بعد ذلك يمكنك إعادة استخدام v من أجل تبادل المقبل.من أجل فرز, تحتاج فقط خوارزمية أن يقول الذي قيم العملات.يمكنك البحث عن خوارزمية مناسبة على سبيل المثال في http://en.wikipedia.org/wiki/Sorting_algorithm .